BOJ10523 직선 찾기

문제 링크 : https://www.acmicpc.net/problem/10523

문제 요약

N개의 점이 좌표 평면 상에 있을 때, 이 중 p 퍼센트 이상의 점들을 지나는 직선이 존재하는지 판별하는 문제다.

문제 풀이

만약 조건을 만족하는 직선이 존재한다면 랜덤하게 두 점을 집었을 때 그 두 점이 만족하는 진선 위에 있을 확률은 \( p^2 \) 일 것이다. 문제에서 \( p >= 0.2 \) 이므로 몬테카를로 알고리즘을 적용 시킬 수 있다.

N=1인 경우에 유의하자.

소스코드 (c++)

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REP2(i,s,e) for(int i=s; i<e; i++)


#define ll long long
#define pii pair<int, int>

#define x first
#define y second

int n, p;

int count(vector< pii > &pts, int p, int q)
{
    pii vec_pq = {pts[q].x-pts[p].x, pts[q].y-pts[p].y};

    vector< pii > others;
    int r = 0;
    for(pii &pt : pts)
    {
        pii vec_v = {pt.x-pts[p].x, pt.y-pts[p].y};
        if(1LL*vec_pq.x*vec_v.y - 1LL*vec_pq.y*vec_v.x == 0) r++;
    }

    return r;
}

int main()
{
    scanf("%d%d", &n, &p);
    vector< pii > pts(n);
    REP(i, n) scanf("%d%d", &pts[i].x, &pts[i].y);

    bool flag = false;
    knuth_b gen;
    int iter = 100;

    if(n == 1) flag = true;

    if(n < 100)
    {
        REP(i, n) REP2(j, i+1, n)
        {
            flag |= count(pts, i, j)*100 >= n*p;
            if(flag) break;
        }
    }

    while(iter--)
    {
        int x = gen() % n;
        int y = gen() % n;
        if(x == y) continue;

        flag |= count(pts, x, y)*100 >= n*p;
        if(flag) break;
    }

    printf("%s\n", flag ? "possible" : "impossible");


    return 0;
}