BOJ)13352 석양이 진다...

문제: icpc.me/13352

n개의 점들이 주어질 때 두직선만으로 모든 점을 커버가능한지 판별하는 문제이다.

얼마전 코포 B번에서 유사한 문제 http://codeforces.com/contest/849/problem/B 가 등장하였지만

코포 문제는 N^2으로 해결할 수 있었던 반면

이 문제는 N제한이 10만이기 때문에 N^2으로는 풀 수 없다.

그래서 정해를 생각해보다가 도저히 떠오르지 않아서 작년에 들었던 야매 풀이를 떠올려서 풀었다.

풀이는 랜덤하게 두 점을 뽑아서 직선을 하나 만든 다음

나머지 모든 점이 한 직선으로 놓일 수 있는지 확인한다.

여기서 나머지 모든 점이 한 직선으로 놓인다면 당연히 두직선으로 커버되는 것이니 답이 되고 안된다면 위의 행동을 반복한다.

위의 행동을 충분히 반복하였는데도 불가능하다고 판별된다면 불가능한다고 답을 출력해도 된다.

만약 답이 success라고 생각하였을 때 한번의 동작에서 안된다고 판별하는 경우는 서로 다른 직선에 있는 두점을 선택하는 경우이다

이런 확률은 1/4정도이므로 이터레이터를 충분히 돌릴경우 로또 맞을 확률이 아닌 이상 통과할 수 있다.

#include <cstdio>
#include <algorithm>
#include <time.h>
#include <vector>
#include <set>
#define INF 1e9
using namespace std;
int n;
pair<double, double> d[100010];
int uc(int x, int y) {
    return y%x ? uc(y%x, x) : x;
}
pair<int,int> getslope(int f, int s) {
    auto l = d[f], r = d[s];
    if (l > r)swap(l, r);
    int diffx = (r.first - l.first);
    int diffy = (r.second - l.second);
    if (!diffx)
        return{ 0,INF };
    else if (!diffy)
        return{ INF,0 };
    else {
        int gcd = uc(diffx, diffy);
        return{ diffx / gcd,diffy / gcd };
    }
}
bool process(int f, int s) {
    auto slope = getslope(f, s);
    vector<int> rem;
    for (int i = 0; i < n; i++) {
        if (i == f)continue;
        auto curr = getslope(f, i);
        if (slope != curr)
            rem.push_back(i);
    }
    if (rem.size() <= 1)return true;
    set<pair<int, int>> st;
    for (auto next : rem) {
        if (next == rem[0])continue;
        auto curr = getslope(rem[0], next);
        st.insert(curr);
    }
    return st.size() == 1 ? 1 : 0;
}
int main() {
    srand(time(NULL));
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lf%lf", &d[i].first, &d[i].second);
    if (n <= 3) {
        puts("success");
        return 0;
    }
    for (int i = 0; i < 5; i++) {
        int x = rand() % n;
        int y = x;
        while (y == x)
            y = rand() % n;
        if (process(x, y)) {
            puts("success");
            return 0;
        }
    }
    puts("failure");
    return 0;
}