[BOJ 10523] 직선 찾기

https://www.acmicpc.net/problem/10523

10523번: 직선 찾기

Tag : random

 

문제요약

N개의 점이 이차원 좌표평면 위에 있을 때 이 중 p퍼센트 이상의 점을 지나는 직선이 있는지 판별하라.

 

풀이

답이 possible이면서 시간복잡도 상으로 최악일 경우를 생각해보자.

k = \( \lfloor \frac{n \times p}{100} \rfloor \)일 때

k개의 점을 지나는 직선이 딱 1개 있는 경우일 것이다.

 

서로 다른 두 점을 아무렇게나 한번 골라서 이 두 점을 지나는 직선이 답에 해당하는 직선일 확률은 다음과 같다.

 

전체 경우 = \(\binom{n}{2}\)

직선에 포함되는 점을 고르는 경우 = \( \binom{ k }{ 2} \)

 

따라서 \( \frac{\binom{ k }{ 2}}{\binom{n}{2}} \)가 아무렇게나 서로 다른 두점을 골라서 직선을 만들어봤을 때

그 직선이 맞는 답에 해당하는 직선일 확률이고

틀릴 확률은 \( \frac{\binom{n}{2} - \binom{ k }{ 2}}{\binom{n}{2}} \)가 된다.

이것이 최대가 되는 경우는 당연히 k가 가장 작은 경우일 것이고

p의 최소인 20을 대입하면 \(\frac{\binom{n}{2}}{10}\)이다.

이 k를 대입하면 틀릴 확률의 최대는 \( \frac{4}{5} \)가 된다. 

이것을 대충 100번만 반복해도 틀릴 확률은 약 2e-8%가 되기 때문에

랜덤으로 두 점을 뽑아보는 풀이가 통과한다.

 

랜덤이라 그런지 똑같은 횟수를 돌렸는데 한번은 틀리고 한번은 맞는 신기한 경험을 했다

맞은사람 1등 기분최고

 

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

struct RAND {
    random_device rg;
    mt19937 rd;
    RAND() { rd.seed(rg()); }
    int nxt(int l, int r) { return uniform_int_distribution<int>(l, r)(rd); }
} rnd;

ll n, pp, f = 0;
ll x[101010], y[101010];

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
int z[36];
char*c=(char*)mmap(0,z[12],1,2,0,fstat(0,(struct stat *)z));
struct fastio {
    inline int f(){int x=0;bool e;c+=e=*c=='-';while(*c>='0')x=10*x+*c++-'0';c++;return e?-x:x;}
} IO;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    n = IO.f(); pp = IO.f();
    if(n == 1) return cout << "possible" << endl, 0;
    for(int i=1; i<=n; i++) x[i] = IO.f(), y[i] = IO.f();
    for(int t=1; t<=150; t++) {
        ll p = rnd.nxt(1, n - 1);
        ll q = rnd.nxt(p + 1, n);
        ll a = y[p] - y[q];
        ll b = x[p] - x[q];
        ll cnt = 0;
        for(int i=1; i<=n; i++) {
            if(a * (x[i] - x[p]) == b * (y[i] - y[p])) cnt++;
        }
        if(cnt >= (n * pp + 99) / 100) {
            f = 1;
            break;
        }
    }
    if(f) cout << "possible" << endl;
    else cout << "impossible" << endl;
}