BOJ 10523 - 직선 찾기 링크
(2023.08.11 기준 P5)

문제

n개의 점이 주어질 때, 이 중 p 퍼센트 이상의 점들을 지나는 직선이 있는지 판별

알고리즘

직선 판별을 위한 ccw 및 무작위화

풀이

일단 직선 판별은 간단하게 ccw로 하면 된다. 세 점의 ccw가 0일 땐, 그 세 점은 직선을 이룬다.

그런데 n이 최대 100,000 이라서 모든 두 점 쌍을 직선으로 두고 나머지 점들을 검사하긴 무리가 있어보인다.
그래서 무작위화를 사용할 것이다.

일단, 임의의 두 점을 잡고, 그 두 점을 잇는 직선에 점이 몇개나 포함되는지 확인해서 조건에 맞는 직선인지 확인해보자. 아마, 아주 높은 확률로 아닐 것이다.
그런데 이 작업을 수없이 반복한다면? 계속 틀릴 확률이 점점 내려간다. 이와 같은 확률론을 이용한 것이 무작위화이다.

물론, 이런 휴리스틱이 항상 100퍼센트 맞진 않는다. 지지리도 운이 없으면...? 하지만, 틀릴 확률이 아주아주 적기 때문에, 웬만하면 AC를 받을 것이다. 기도하자

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

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

// 난수 설정
random_device rd;
mt19937 generator(rd());

ll ccw(pll a, pll b, pll c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

int randint(int l, int r){
    return uniform_int_distribution<int> (l, r)(generator);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // 점의 개수가 2개 이하라면 무조건 가능하다.
    int n; cin >> n;
    if (n <= 2){
        cout << "possible";
        return 0;
    }

    // 지나야 하는 점의 개수가 2개 이하라면 무조건 가능하다.
    int p; cin >> p;
    int m = ceil(n * p * 0.01);
    if (m <= 2){
        cout << "possible";
        return 0;
    }

    pll points[n];
    for (int i = 0; i < n; i++) cin >> points[i].x >> points[i].y;

    time_t st = time(0); // 시작 시간 체크
    while (true){

        // 직선의 양 끝점이 될 두 점을 무작위로 뽑는다.
        vector<pll> ends;
        while (ends.size() < 2){
            pll p = points[randint(0, n - 1)];
            if (find(ends.begin(), ends.end(), p) == ends.end()){
                ends.push_back(p);
            }
        }

        // 양 끝점과 ccw가 0인 점의 개수를 구한다.
        int result = 0;
        for (int i = 0; i < n; i++) if (!ccw(ends[0], ends[1], points[i]))
            if (++result == m) break;

        // 지나야 하는 점의 개수를 도달했다면 성공
        if (result == m){
            cout << "possible";
            break;
        }

        // 시작 시간으로부터 3초가 지났다면 불가능한 것으로 간주하고 종료
        if (time(0) - st > 3){
            cout << "impossible";
            break;
        }
    }
}

• Python

import sys; input = sys.stdin.readline
from math import ceil
from time import time
from random import randint

def ccw(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])

# 점의 개수가 2개 이하라면 무조건 가능하다.
n = int(input())
if n <= 2:
    print('possible')
    exit()

# 지나야 하는 점의 개수가 2개 이하라면 무조건 가능하다.
p = int(input())
m = ceil(n * p * 0.01)
if m <= 2:
    print('possible')
    exit()

points = [tuple(map(int, input().split())) for _ in range(n)]

st = time() # 시작 시간 체크
while True:

    # 직선의 양 끝점이 될 두 점을 무작위로 뽑는다.
    ends = []
    while len(ends) < 2:
        p = points[randint(0, n - 1)]
        if p not in ends:
            ends.append(p)

    # 양 끝점과 ccw가 0인 점의 개수를 구한다.
    result = 0
    for i in range(n):
        if not ccw(ends[0], ends[1], points[i]):
            result += 1
            if result == m:
                break

    # 지나야 하는 점의 개수를 도달했다면 성공
    if result == m:
        print('possible')
        break

    # 시작 시간으로부터 10초가 지났다면 불가능한 것으로 간주하고 종료
    if time() - st > 10:
        print('impossible')
        break