10523 - 직선 찾기

 

 

step 1

이 문제의 $p$의 최솟값이 20입니다. 왜 굳이 20으로 했을까요?

step 2

답이 있다고 가정해 봅시다. 임의의 점 하나를 찍었을 때 해당 점이 선 위에 있을 확률은 $\frac{p}{100}$입니다. 그럼 서로 다른 두 점을 찍었을 때 두 점 다 선 위에 있을 확률은 $\frac{p*p}{100*100} \ge \frac{1}{25}$입니다. 그럼

1. 아무 두 점을 잡습니다.
2. 이 직선 위에 점이 $p\%$이상 있는지 확인합니다.
3. 엄청 반복합니다.

한 스텝 확인하는데 $N$만큼의 시간이 걸립니다. 그럼 500번쯤 돌리면 $p$가 20일 때 1.3665e-9의 확률로 틀릴 수 있습니다. 이정도 돌렸는데 직선을 못 찾았다면 그건 원래 직선이 없었다 보는게 맞겠죠

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<map>
#include<math.h>
#include<queue>
#include<time.h>
#include<stdlib.h>
using namespace std;
struct data {
	long long int x, y;
}b[200000];
long long int ccw(long long int x, long long int y, long long int z) {
	return
		b[x].x * b[y].y + b[y].x * b[z].y + b[z].x * b[x].y - b[y].x * b[x].y - b[z].x * b[y].y - b[x].x * b[z].y;
}
int main() {
	long long int n, i,p,j;
	srand(time(NULL));
	scanf("%lld %lld", &n, &p);
	for (i = 1; i <= n; i++) {
		scanf("%lld%lld", &b[i].x, &b[i].y);
	}
	if (n == 1) { printf("possible"); return 0; }
	for (i = 1; i <= 1000; i++) {
		long long int x = 1ll * rand() * rand() % n+1;
		long long int y = 1ll * rand() * rand() % n+1;
		if (x == y) continue;
		long long int cnt = 0;
		for (j = 1; j <= n; j++) {
			if (ccw(x, y, j) == 0) cnt++;
		}
		if (cnt * 100 >= p * n) {
			printf("possible"); return 0;
		}
	}
	printf("impossible");
	return 0;
}