step 1
step 2
더보기
더보기
답이 있다고 가정해 봅시다. 임의의 점 하나를 찍었을 때 해당 점이 선 위에 있을 확률은 $\frac{p}{100}$입니다. 그럼 서로 다른 두 점을 찍었을 때 두 점 다 선 위에 있을 확률은 $\frac{p*p}{100*100} \ge \frac{1}{25}$입니다. 그럼
- 아무 두 점을 잡습니다.
- 이 직선 위에 점이 $p\%$이상 있는지 확인합니다.
- 엄청 반복합니다.
한 스텝 확인하는데 $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;
}
'PS - 알고리즘' 카테고리의 다른 글
6496 - Cyclic antimonotonic permutations (0) | 2024.07.18 |
---|---|
16570 - 앞뒤가 맞는 수열 (0) | 2024.07.11 |
1090 - 체커 (0) | 2024.07.11 |
30294 - Flea (1) | 2024.07.05 |
14679 - 영우와 ‘갓4’ (0) | 2024.07.05 |