티스토리 뷰

알고리즘 관련/BOJ

BOJ)13352 석양이 진다...

JASON 자손9319 2017. 9. 7. 03:26

문제: icpc.me/13352


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


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


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


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


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


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


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


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


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


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


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


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
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <algorithm>
#include <time.h>
#include <vector>
#include <set>
#define INF 1e9
using namespace std;
int n;
pair<doubledouble> 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)
        return0,INF };
    else if (!diffy)
        return{ INF,};
    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<intint>> st;
    for (auto next : rem) {
        if (next == rem[0])continue;
        auto curr = getslope(rem[0], next);
        st.insert(curr);
    }
    return st.size() == 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;
}
cs



'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)5542 JOI 국가의 행사  (0) 2017.09.12
BOJ)13330 유사 팰린드롬  (0) 2017.09.08
BOJ)13352 석양이 진다...  (1) 2017.09.07
BOJ)5842 Partitioning the Farm  (0) 2017.09.07
BOJ)2337 트리 자르기  (1) 2017.09.05
BOJ)11003 최소값 찾기  (1) 2017.09.05
TAG
댓글
  • 프로필사진 Esanghannoms 코딩은 안해봤지만 풀이를 생각해봤습니다
    세 점을 골라봅시다. 어떻게 고르던, 만약 모든 점들이 두 직선만으로 해결이 가능한 경우, 비둘기집의 원리에 의해 그 두 직선 중 하나의 직선에 동시에 포함되는 두 점이 존재할 것입니다.
    그래서 세 점을 골라서 만들 수 있는 삼각형의 세 변을 연장하여 만든 직선에 대해, 그 직선 상에 있는 세 점을 이어 보고 남은 점들이 한 직선 상에 있는지 판단해 봅시다. 만약 문제의 답이 yes 라면 이 세 번 안에 답을 찾아낼 수 있을 것이고, 그렇지 못한 경우 불가능을 출력하면 될 것 같습니다.
    2018.06.11 19:05
댓글쓰기 폼