백준3323 삼각형

작성일 | In

문제 링크

  • http://icpc.me/3323

문제 출처

  • 2009 CEOI Day2 3번

사용 알고리즘

  • 세그먼트 트리
  • 볼록 껍질
  • 삼분 탐색 / 파라메트릭 서치

시간복잡도

  • $O(N \log N + Q \log^2 N)$

풀이

각도 범위 안에 있는 점들 중, 주어진 선분 아래에 점이 있는지 판별하면 됩니다.

각도 제한이 없고, 선분이 아닌 직선이 주어지는 문제를 먼저 풀어봅시다.
점들의 Convex Hull을 구한 뒤, 삼분탐색을 통해서 찾은 가장 아래에 있는 점(직선 위의 임의의 두 점을 잡았을 때, Signed Area을 최대화하는 점)을 찾아서 직선 아래에 있는지 판별하면 됩니다.

각도 제한이 있어도 비슷하게 문제를 풀 수 있습니다. 주어진 모든 점의 Convex Hull을 구하는 것 대신, 각도 범위 안에 있는 점들로만 Convex Hull을 구하면 됩니다.
주어진 점을 각도 순으로 정렬한 다음, Convex Hull을 관리하는 Segment Tree를 만들면 효율적으로 판별할 수 있습니다.

전체 코드

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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())
using namespace std;

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

ll area(const p &a, const p &b, const p &c){
    ll dx1 = b.x - a.x, dy1 = b.y - a.y;
    ll dx2 = c.x - b.x, dy2 = c.y - b.y;
    return dx1*dy2 - dx2*dy1;
}
int ccw(const p &a, const p &b, const p &c){
    ll res = area(a, b, c);
    return (res > 0) - (res < 0);
}
ll dst(const p &a, const p &b){
    ll dx = a.x - b.x, dy = a.y - b.y;
    return dx*dx + dy*dy;
}
bool cmp(const p &p1, const p &p2){
    static const p O(0, 0);
    int cw = ccw(O, p1, p2);
    if(cw) return cw > 0;
    return dst(O, p1) < dst(O, p2);
}

struct Seg{
    vector<p> tree[1 << 18];
    static const int sz = 1 << 17;
    void insert(int x, p v){ for(x|=sz; x; x>>=1) tree[x].push_back(v); }
    void build(){ for(int i=1; i<sz+sz; i++) __make_hull(i); }
    bool chk(int node, p s, p e){
        if(tree[node].empty()) return false;
        int l = 0, r = tree[node].size()-1;
        while(l+3 < r){
            int m1 = (l+l+r) / 3, m2 = (l+r+r) / 3;
            if(area(s, e, tree[node][m1]) < area(s, e, tree[node][m2])) l = m1;
            else r = m2;
        }
        for(int i=l; i<=r; i++) if(ccw(s, e, tree[node][i]) > 0) return true;
        return false;
    }
    bool query(int l, int r, p s, p e){
        l |= sz; r |= sz;
        while(l <= r){
            if(l & 1 && chk(l++, s, e)) return true;
            if(~r & 1 && chk(r--, s, e)) return true;
            l >>= 1; r >>= 1;
        }
        return false;
    }
    void __make_hull(int node){
        vector<p> hull;
        vector<p> &pt = tree[node];
        //sort(all(pt), cmp);
        for(auto i : pt){
            while(hull.size() >= 2 && ccw(hull[hull.size()-2], hull.back(), i) >= 0) hull.pop_back();
            hull.push_back(i);
        }
        pt = hull;
    }
} seg;

int n, q;
p a[101010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i].x >> a[i].y;
    sort(a+1, a+n+1, cmp);
    for(int i=1; i<=n; i++) seg.insert(i, a[i]);
    seg.build();
    for(int i=1; i<=q; i++){
        p s, e; cin >> s.x >> s.y >> e.x >> e.y;
        if(ccw(a[0], s, e) < 0) swap(s, e);
        int l = lower_bound(a+1, a+n+1, s, cmp) - a;
        int r = upper_bound(a+1, a+n+1, e, cmp) - a - 1;
        if(seg.query(l, r, s, e)) cout << "Y\n";
        else cout << "N\n";
    }
}