백준10523 직선 찾기

작성일 | In

문제 링크

  • http://icpc.me/10523

문제 출처

  • 2014 NWERC 2014 F번

사용 알고리즘

  • 랜덤!

풀이

정해는 분할 정복이라고 하지만, 분할 정복은 어렵기 때문에 이상한 전략을 생각해봅시다.

직선이 존재하는지/존재하지 않는지 판단만 하면 됩니다.
두 점을 랜덤으로 잡아서 만든 직선 위에 P% 이상의 점이 있는지 판단하는 전략을 생각해볼 수 있습니다.
시간 제한 안에서 돌아갈 정도로만 랜덤을 돌려주면서 P% 이상의 점이 존재하는 직선이 있으면 possible을, 못 찾았으면 impossible를 출력하면 됩니다.

실제로 150번정도만 확인해보면 매우 높은 확률로 맞고, 100번정도 확인해도 꽤 높은 확률로 맞습니다.
80번정도 확인하는 코드를 짠 다음에 신중하게 제출하면 맞을 수 있긴 합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

mt19937 rd;

ll n, per;
ll want;
vector<p> v;

int cnt(p x, p y){
	int ret = 0;
	for(auto i : v){
		ret += (y.y - x.y)*(i.x - x.x) == (i.y - x.y)*(y.x - x.x);
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> per; v.resize(n);
	if(n == 1){
		cout << "possible"; return 0;
	}
	if(n*per%100 == 0) want = n*per/100;
	else want = n*per/100+1;
	for(int i=0; i<n; i++) cin >> v[i].x >> v[i].y;

	rd = mt19937((unsigned)chrono::steady_clock::now().time_since_epoch().count());
	uniform_int_distribution<int> ran(0, n-1);

	for(int loop=0; loop<150; loop++){
		int a = ran(rd);
		int b = ran(rd);
		while(a == b) b = ran(rd);
		if(cnt(v[a], v[b]) >= want){
			cout << "possible"; return 0;
		}
	}
	cout << "impossible";
}