Dividing_Area

题目传送门
题意:
给你$n$个点,有$Q$次操作,操作分别为在两个点之间连一条边和询问在一条边左边的相邻的封闭图形的面积。
并且最后$n$个点会形成一个平面图。

我们把操作离线,对最后的平面图进行转对偶图操作,把每条边拆成两条单向边,并且用并查集把有向边左边的空白区域和该边连接起来,树根为空白区域,并记录空白区域面积。
然后倒着操作,如果是加边操作,则删除该边,并把两个有向边所相邻的空白区域用并查集合并,查询面积操作即访问树根即可。
NOTE:极角排序写挫了、、RE20不能自拔……

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
//created by missever
#include<bits/stdc++.h>
#define MAX 1000000007
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
typedef pair<double,int> PD;
const int maxn = 1e6 + 5;
const double eps = 1e-10;
const double pi = acos(-1);
inline int sgn(double x) {
if(x < -eps) return -1;
else if(x > eps) return 1;
else return 0;
}
struct Point {
int x,y;
Point(int _x = 0,int _y = 0): x(_x),y(_y) {}
Point operator + (const Point &b) const {
return Point(x + b.x,y + b.y);
}
Point operator - (const Point &b) const {
return Point(x - b.x,y - b.y);
}
LL operator * (const Point &b) const {
return (1LL * x * b.x + 1LL * y * b.y);
}
LL operator ^ (const Point &b) const {
return (1LL * x * b.y - 1LL * y * b.x);
}
};
Point p[maxn];
P f[maxn];
struct que {
int op,u,v;
que(int _op = 0,int _u = 0,int _v = 0): op(_op),u(_u),v(_v) {}
} q[maxn];
int n,tot = 0;
bool vis[maxn * 2];
map<P,int> mp;
vector<PD> g[maxn];
int df[maxn * 4];
map<int,LL> mpp;
map<int,int> gg[maxn];
LL sm = 0;
int sk;
LL ans[maxn];
double get_ang(int u,int v) {
return atan2(p[v].y - p[u].y,p[v].x - p[u].x);
}
int fff(int x) {
if(df[x] != x) df[x] = fff(df[x]);
return df[x];
}
void work(int u,PD e) {
int v1 = u,v2 = e.second,k = 0;
f[k++] = P(v1,v2);
while(v2 != u) {
v1 = gg[v2][v1];
if(v1 == 0) v1 = g[v2].back().second;
else v1 = g[v2][v1 - 1].second;
swap(v1,v2);
f[k++] = P(v1,v2);
}
LL ss = 0;
for(int i = 0; i < k; i++) ss += p[f[i].first] ^ p[f[i].second];
if(ss <= 0) mpp[tot] = -1;
else mpp[tot] = ss;
df[tot] = tot;
for(int i = 0; i < k; i++) {
int j = mp[f[i]];
vis[j] = 1;
df[j] = tot;
}
tot++;
}
bool cmp(const PD &a,const PD &b){
if(sgn(b.first - a.first) == 0) return ((p[b.second] - p[sk]) ^ (p[a.second] - p[sk])) < 0;
else return b.first - a.first > eps;
}
void build() {
int i,j;
for(i = 1; i <= n; i++){
sk = i;
sort(g[i].begin(),g[i].end(),cmp);
for(j = 0;j < g[i].size(); j++) gg[i][g[i][j].second] = j;
}
for(i = 1; i <= n; i++) {
for(auto e:g[i]) {
j = mp[P(i,e.second)];
if(vis[j]) continue;
work(i,e);
}
}
}
int main() {
int Q,i,op,u,v;
scanf("%d",&n);
for(i = 1; i <= n; i++) scanf("%d%d",&p[i].x,&p[i].y);
scanf("%d",&Q);
for(i = 1; i <= Q; i++) {
scanf("%d%d%d",&op,&u,&v);
u++;
v++;
q[i] = que(op,u,v);
if(op == 1) {
g[u].push_back(PD(get_ang(u,v),v));
g[v].push_back(PD(get_ang(v,u),u));
mp[P(u,v)] = tot++;
mp[P(v,u)] = tot++;
}
}
build();
int tt = 0;
for(i = Q; i > 0; i--) {
if(q[i].op == 1) {
u = fff(mp[P(q[i].u,q[i].v)]);
v = fff(mp[P(q[i].v,q[i].u)]);
if(u == v) continue;
if(mpp[u] == -1 || mpp[v] == -1) mpp[u] = -1;
else mpp[u] += mpp[v];
df[v] = u;
} else {
u = fff(mp[P(q[i].u,q[i].v)]);
ans[tt++] = mpp[u];
}
}
for(i = tt - 1; i >= 0; i--) printf("%lld\n",ans[i]);
return 0;
}