[백준 13352] 석양이 진다

무작위화로 처음 푸는 문제이다. 되게 흥미로웠다.

1. 풀이

무작위로 직선을 긋고 다음 직선을 긋는 다고 생각해보자. 어느 한 직선을 그으면 나머지 직선에서는 알아서 그어지니 고려안해도 된다. 이 방법에서는 두 직선이 각 \(\frac{N}{2}\)개씩 지나는 경우가 최악의 케이스가 된다.

이 경우에 확률을 구해보자.
$$\frac{\frac{N}{2}}{N}∗\frac{\frac{N}{2}−1}{N−1}=\frac{N−2}{4(N−1)}≓0.25$$
즉 최악의 케이스에도 고를 확률이 \(0.25\)니 적절하게 반복해주면 끝난다.

2.소스 코드

#include <bits/stdc++.h>
#include <random>
 
using namespace std;
 
typedef long long ll;
 
struct vec2 {
    ll x, y;
};
 
bool ccw(vec2 a, vec2 b, vec2 c) {
    ll s = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
 
    return s == 0;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int n; cin >> n;
    vector<vec2> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i].x >> arr[i].y;
 
    if (n <= 4) {
        cout << "success";
        return 0;
    }
 
    function<int()> myrand = [&]() -> int {
        std::random_device rd;
        std::mt19937 mt(rd());
        std::uniform_int_distribution<int> dist(0, n-1);
 
        return dist(mt);
    };
 
    int k = 100;
    bitset<100001> visit;
    for (int i = 1; i <= k; i++) {
        visit.reset();
 
        vector<int> can;
        while (can.size() < 4) {
            int t = myrand();
            while (visit[t]) t = myrand();
 
            visit[t] = true;
            can.push_back(t);
        }
 
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (ccw(arr[can[0]], arr[can[1]], arr[j]) ||
                ccw(arr[can[2]], arr[can[3]], arr[j]))
                cnt++;
        }
 
        if (cnt == n) {
            cout << "success";
            return 0;
        }
    }
    
    cout << "failure";
    return 0;
}