백준17442 삼분 그래프

작성일 | In

문제 링크

  • http://icpc.me/17442

사용 알고리즘

  • 듀얼 그래프

풀이

평면 그래프에서는 $V-E+F=C+1$가 성립합니다.
그래프에 변형을 가했을 때 컴포넌트 개수의 변화량 $\Delta C$는 $\Delta V - \Delta E + \Delta F$입니다. 주어진 그래프에서 $C = 1$이므로 $\Delta C+1 = \Delta V - \Delta E + \Delta F + 1$을 구하면 됩니다.

직선 A, B로 그래프를 삼분한다고 합시다.

  • $\Delta E = $ (A를 지나는 간선의 개수 + B를 지나는 간선의 개수)
  • $\Delta V = $ 2(A를 지나는 간선의 개수 + B를 지나는 간선의 개수) $ = 2\Delta E$
  • $\Delta F = $ -(A 혹은 B를 지나는 면의 개수)
  • $\Delta C = \Delta V - \Delta E + \Delta F = \Delta E + \Delta F$

$\Delta E$는 간선의 양 끝점의 x좌표를 구한 뒤 변홧값 배열을 통해 쉽고 빠르게 구할 수 있습니다. $\Delta F$를 빠르게 구해야 합니다.

y축에 평핸한 직선을 그어서 face를 분할하는 것이므로, 일단 각 face의 x좌표 범위를 구해봅시다. face의 x좌표 범위는 Dual Graph를 만드는 느낌으로 Union Find를 해주면 구할 수 있습니다.
face의 x좌표 범위를 $[L, R]$이라고 합시다. 모든 face에 대해 $[L, R]$을 구해서 2차원 평면 상에 플로팅해줍시다. $L \leq R$이기 때문에 모든 점은 $y = x$ 그래프 위쪽에 있습니다.

직선 A, B에 의해서 x좌표 범위가 $[L, R]$인 face가 잘리기 위해서는 $L \leq A$ 또는 $B \leq R$를 만족해야 합니다.

$L \leq A$를 만족하는 점들은 아래 그림의 빨간색 영역 안에 있는 점들입니다.

$B \leq R$을 만족하는 점들은 아래 그림의 파란색 영역 안에 있는 점들입니다.

$L \leq A$ 또는 $B leq R$을 만족하는 점들의 개수를 구하기 위해서는 빨간색 영역 안에 있는 점들의 개수와 파란색 영역 안에 있는 점들의 개수를 구해서 더한 뒤, 아래 그림의 파란색 영역 안에 있는 점들의 개수를 빼주면 됩니다.

직사각형 영역에 있는 점의 개수는 PST나 Merge Sort 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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#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;

int par[404040], id[404040];
int _l[404040], _r[404040];
int l[404040], r[404040];
int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
void merge(int u, int v){
    u = find(u), v = find(v);
    if(u ^ v) par[u] = v, _l[v] = min(_l[v], _l[u]), _r[v] = max(_r[v], _r[u]);
}
ll ccw(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;
    ll res = dx1*dy2 - dx2*dy1;
    if(res > 0) return 1;
    if(res) return -1;
    return 0;
}

int n, m, q;
p pt[101010];
vector<p> g[404040];
vector<int> dual_pt;

p base;
bool cmp_angle(const p &_a, const p &_b){
    p a = pt[_a.x], b = pt[_b.x];
    if((a > base) != (b > base)) return a > b;
    return ccw(a, base, b) > 0;
}

int out;
void getDual(){
    iota(par, par+404040, 0);
    for(int i=1; i<=n; i++){
        base = pt[i];
        sort(all(g[i]), cmp_angle);
        for(int j=0; j<g[i].size(); j++){
            int k = j ? j-1 : g[i].size()-1;
            int u = g[i][k].y << 1 | 1, v = g[i][j].y << 1;
            p p1 = pt[g[i][k].x], p2 = pt[g[i][j].x];
            if(p1 > base) u ^= 1;
            if(p2 > base) v ^= 1;
            merge(u, v);
        }
    }
    for(int i=1; i<=m; i++){
        id[i << 1] = find(i << 1);
        id[i << 1 | 1] = find(i << 1 | 1);
    }
    int mnidx = min_element(pt+1, pt+n+1) - pt;
    out = id[g[mnidx][0].y << 1 | 1];
    for(int i=1; i<=m; i++){
        dual_pt.push_back(id[i << 1]);
        dual_pt.push_back(id[i << 1 | 1]);
    }
    compress(dual_pt);
    for(int i=0; i<dual_pt.size(); i++){
        l[i] = _l[dual_pt[i]]; r[i] = _r[dual_pt[i]];
    }
    for(int i=1; i<=m; i++){
        id[i << 1] = lower_bound(all(dual_pt), i << 1) - dual_pt.begin();
        id[i << 1 | 1] = lower_bound(all(dual_pt), i << 1 | 1) - dual_pt.begin();
    }
    out = lower_bound(all(dual_pt), out) - dual_pt.begin();
}

vector<int> comp;
vector<int> tree[1 << 20];
int sz = 1 << 19;
void add(int x, int v){ tree[x|sz].push_back(v); }
int query(int l, int r, int L, int R){
    l |= sz; r |= sz; int ret = 0;
    while(l <= r){
        if(l & 1){
            ret += upper_bound(all(tree[l]), R) - lower_bound(all(tree[l]), L); l++;
        }
        if(~r & 1){
            ret += upper_bound(all(tree[r]), R) - lower_bound(all(tree[r]), L); r--;
        }
        l >>= 1, r >>= 1;
    }
    return ret;
}
void build(){
    for(int i=sz; i<sz+sz; i++) if(tree[i].size() >= 2) sort(all(tree[i]));
    for(int i=sz-1; i; i--) merge(all(tree[i << 1]), all(tree[i << 1 | 1]), back_inserter(tree[i]));
}

int sum[303030];
void preProcess(){
    for(int i=1; i<=n; i++) for(int j=-1; j<=1; j++) comp.push_back(pt[i].x+j);
    compress(comp);
    for(int i=1; i<=n; i++){
        for(auto j : g[i]){
            if(pt[i] > pt[j.x]) continue;
            int a = lower_bound(all(comp), pt[i].x) - comp.begin() + 1;
            int b = lower_bound(all(comp), pt[j.x].x) - comp.begin() + 1;
            sum[a]++; sum[b]--;
        }
    }
    for(int i=0; i<dual_pt.size(); i++){
        if(i == out) continue;
        l[i] = lower_bound(all(comp), l[i]) - comp.begin() + 1;
        r[i] = lower_bound(all(comp), r[i]) - comp.begin() + 1;
        add(l[i], r[i]);
    }
    build();
    for(int i=1; i<303030; i++) sum[i] += sum[i-1];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    for(int i=1; i<=n; i++) cin >> pt[i].x >> pt[i].y;
    for(int i=1; i<=m; i++){
        int s, e; cin >> s >> e;
        g[s].emplace_back(e, i);
        g[e].emplace_back(s, i);
        _l[i << 1] = _l[i << 1| 1] = min(pt[s].x, pt[e].x);
        _r[i << 1] = _r[i << 1| 1] = max(pt[s].x, pt[e].x);
    }
    getDual();
    preProcess();

    for(int i=1; i<=q; i++){
        int a, b; cin >> a >> b;
        a = lower_bound(all(comp), a) - comp.begin() + 1;
        b = lower_bound(all(comp), b) - comp.begin() + 1;
        int e = sum[a] + sum[b];
        int f = query(1, a, a, 303000) + query(1, b, b, 303000) - query(1, a, b, 303000);
        cout << e-f+1 << "\n";
    }
}