백준13352 석양이 진다...

작성일 | In

문제 링크

  • http://icpc.me/13352

문제 출처

  • 2016 BAPC 예선 J번

사용 알고리즘

  • 랜덤

시간복잡도

  • $O(N \cdot iteration)$

풀이

두 점을 랜덤으로 선택해서 직선을 하나 만들고, 그 직선에 포함되지 않은 점들을 다른 한 직선으로 커버할 수 있는지 확인하는 랜덤 풀이를 시도해볼 수 있습니다. 점이 $N$개 있고, 두 직선에 점이 각각 $a, b$개($a+b=N$) 포함된다고 하면, 실제로 정답이 존재할 때 정답을 찾지 못할 확률(실패할 확률)은 $\frac{ab}{N\choose 2} \approx \frac{2ab}{N^2}$입니다.

$a = b = N/2$일 때 실패할 확률이 최대가 되며, 이때 실패할 확률은 대략 $\frac{2 \cdot \frac{N}{2}\cdot\frac{N}{2}}{N^2} = \frac{1}{2}$입니다. 최악의 경우에도 실패할 확률이 $\frac{1}{2}$보다 크지 않기 때문에 이 풀이를 $K$번 반복해서 수행하면 실패할 확률은 $(\frac{1}{2})^K$이하가 되고, 시간 복잡도는 $O(NK)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using coord_t = ll;
using Point = pair<coord_t, coord_t>;

istream& operator >> (istream &in, Point &t){ in >> t.x >> t.y; return in; }
Point    operator  + (Point p1, Point p2){ return {p1.x+p2.x, p1.y+p2.y}; }
Point    operator  - (Point p1, Point p2){ return {p1.x-p2.x, p1.y-p2.y}; }
coord_t  operator  * (Point p1, Point p2){ return p1.x*p2.x + p1.y*p2.y; } /// dot product
coord_t  operator  / (Point p1, Point p2){ return p1.x*p2.y - p2.x*p1.y; } /// cross product

coord_t _CCW(const Point &p1, const Point &p2, const Point &p3){ return (p2-p1)/(p3-p2); }
int CCW(Point p1, Point p2, Point p3){
    auto res = _CCW(p1, p2, p3);
    return (res > 0) - (res < 0);
}
coord_t D(const Point &p1, const Point &p2){
    auto dx = p1.x - p2.x, dy = p1.y - p2.y;
    return dx*dx + dy*dy;
}

int N;
Point A[101010];

mt19937 rd(0x917917);
int rand(int l, int r){
    return uniform_int_distribution<int>(l, r)(rd);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    if(N <= 2){ cout << "success"; return 0; }

    for(int iter=1; iter<=100; iter++){
        vector<Point> P;
        int a = rand(1, N), b = rand(1, N), flag = 1;
        while(a == b) b = rand(1, N);
        for(int i=1; i<=N; i++) if(CCW(A[a], A[b], A[i]) != 0) P.push_back(A[i]);
        for(int i=2; i<P.size(); i++) if(CCW(P[i-2], P[i-1], P[i]) != 0) flag = 0;
        if(flag){ cout << "success"; return 0; }
    }
    cout << "failure";
}