题目
https://gmoj.net/senior/#main/show/3976
题解
这道题目有不少解题的方法，但是大多比较麻烦。这里提供一种简捷的方法（改进自
x
i
a
o
q
i
xiaoqi
xiaoqi大佬的解法）
为了方便，不妨先将所有点平移至第一象限。假设要求出的是简单多边形ABCDE中的青蛙贡献值，各顶点分布如下图所示：
令
n
u
m
△
A
B
C
num_{△ABC}
num△ABC表示△ABC中青蛙的价值之和。 发现这是等于
n
u
m
△
O
A
B
+
n
u
m
△
O
B
C
+
n
u
m
△
O
C
D
−
n
u
m
△
O
E
D
−
n
u
m
△
O
A
E
num_{△OAB}+num_{△OBC}+num_{△OCD}-num_{△OED}-num_{△OAE}
num△OAB+num△OBC+num△OCD−num△OED−num△OAE。不难得出结论：
多边形的num=Σ多边形中的 某些边 与点O所形成的三角形的num-Σ多边形中的 其它边 与点O所形成的三角形的num
我们不妨把这些点极角排序，接着顺时针（或逆时针）扫这些边。假如现在扫到边
A
i
A
i
+
1
A_iA_{i+1}
AiAi+1，如果
A
i
A_i
Ai的极角序大于
A
i
+
1
A_{i+1}
Ai+1的极角序，那么就加上这条边与O形成三角形的num，否则减去这条边的num。这样子结果的绝对值等于答案。
现在问题就是怎么快速求出图中任意一个三角形的num。
考虑割补法，发现对于一个三角形ABO（如下图），
n
u
m
△
A
B
O
=
n
u
m
△
A
O
A
′
−
n
u
m
△
B
O
A
′
num_{△ABO}=num_{△AOA'}-num_{△BOA'}
num△ABO=num△AOA′−num△BOA′（A’是AB的延长线与x轴的交点）。
我们以每个顶点为原点，给所有的青蛙点、顶点以及原点极角排序（这里可以以第三象限最小、第二象限最大的极角值来排序），然后维护一个前缀和数组
s
u
m
i
,
j
sum_{i,j}
sumi,j记录以点 i 为原点，对其他点进行极角排序，其中 j 以及极角值比 j 的要小的点的价值和（这里不妨把顶点和原点视作价值为0的青蛙）。
由于题目保证了无三点共线的情况，而有两点与原点共线的情况又很好处理（只用让原点的极角序比与它极角值相等的点的极角序小就行了），这样就能快速求出
n
u
m
△
A
O
A
′
num_{△AOA'}
num△AOA′了（其实就是
s
u
m
A
,
B
−
s
u
m
A
,
O
sum_{A,B}-sum_{A,O}
sumA,B−sumA,O 。但是
n
u
m
△
B
O
A
′
num_{△BOA'}
num△BOA′怎么求呢？可以在以顶点
A
i
A_i
Ai为原点时，对于每一个顶点
A
j
(
i
≠
j
)
A_j(i\not=j)
Aj(i=j)，都新建一个
A
j
A_j
Aj关于
A
i
A_i
Ai对称的点
A
j
′
A_j'
Aj′，然后和上面一样处理就行了。
时间复杂度
O
(
n
log
(
n
+
m
)
+
∑
s
)
O(n\log(n+m)+\sum s)
O(nlog(n+m)+∑s)。
x
i
a
o
q
i
xiaoqi
xiaoqi大佬在求一个三角形的num时做法不同，他是把以每一个顶点为原点给其它点排好序，算出前缀和。然后询问时用余弦定理算出∠A’OB，二分求价值和。
CODE
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std
;
#define llf long double
#define M 10001
#define N 1005
struct node
{int x
,y
,id
,type
;long double ang
;}a
[N
],b
[N
],c
[3005];
int n
,v
[N
],arr
[N
],sum
[N
][N
],_sum
[N
][N
],edge
[N
][N
];
inline char gc()
{
static char buf
[100005],*l
=buf
,*r
=buf
;
return l
==r
&&(r
=(l
=buf
)+fread(buf
,1,100005,stdin),l
==r
)?EOF:*l
++;
}
inline void read(int &k
)
{
char ch
;bool sign
=0;
while(ch
=gc(),ch
!='-'&&(ch
<'0'||ch
>'9'));
if(ch
=='-') sign
=1,ch
=gc();k
=ch
-'0';
while(ch
=gc(),ch
>='0'&&ch
<='9') k
=k
*10+ch
-'0';
if(sign
) k
=-k
;
}
inline int abs(int x
,int y
){return x
<0?-x
:x
;}
inline bool cmp(node x
,node y
)
{return x
.ang
!=y
.ang
?x
.ang
<y
.ang
:abs(x
.x
)>abs(y
.x
);}
inline int calc(int x
,int y
)
{
int sign
=cmp(a
[x
],a
[y
])?1:-1;
if(sign
>0) x
^=y
,y
^=x
,x
^=y
;
return sign
*(sum
[x
][y
]+sum
[y
][n
+1]-sum
[x
][n
+1]-_sum
[y
][x
]);
}
int main()
{
int m
,q
,k
,s
,cnt
;
read(n
),read(m
);
for(int i
=1;i
<=n
;++i
) read(a
[i
].x
),read(a
[i
].y
),a
[i
].ang
=atan2((llf
)a
[i
].y
,(llf
)a
[i
].x
);
for(int i
=1;i
<=m
;++i
) read(b
[i
].x
),read(b
[i
].y
),read(v
[i
]),b
[i
].ang
=atan2((llf
)b
[i
].y
,(llf
)b
[i
].x
);
for(int i
=1;i
<=n
;++i
) a
[i
].x
+=M
,a
[i
].y
+=M
;
for(int i
=1;i
<=m
;++i
) b
[i
].x
+=M
,b
[i
].y
+=M
;
for(int i
=1;i
<=n
;++i
)
{
s
=1,cnt
=0,c
[1]=(node
){-a
[i
].x
,-a
[i
].y
,n
+1,0};
for(int j
=1;j
<=n
;++j
) if(i
^j
)
c
[++s
]=(node
){a
[j
].x
-a
[i
].x
,a
[j
].y
-a
[i
].y
,j
,0,atan2((llf
)(a
[j
].y
-a
[i
].y
),(llf
)(a
[j
].x
-a
[i
].x
))},
c
[++s
]=(node
){a
[i
].x
-a
[j
].x
,a
[i
].y
-a
[j
].y
,j
,1,atan2((llf
)(a
[i
].y
-a
[j
].y
),(llf
)(a
[i
].x
-a
[j
].x
))};
for(int j
=1;j
<=m
;++j
) c
[++s
]=(node
){b
[j
].x
-a
[i
].x
,b
[j
].y
-a
[i
].y
,j
,2,atan2((llf
)(b
[j
].y
-a
[i
].y
),(llf
)(b
[j
].x
-a
[i
].x
))};
sort(c
+1,c
+s
+1,cmp
);
for(int j
=1;j
<=s
;++j
)
{
if(!c
[j
].type
) sum
[i
][c
[j
].id
]=cnt
;
else if(c
[j
].type
==1) _sum
[i
][c
[j
].id
]=cnt
;
else cnt
+=v
[c
[j
].id
];
}
}
for(int i
=1;i
<=n
;++i
)
for(int j
=1;j
<i
;++j
)
edge
[i
][j
]=calc(i
,j
),edge
[j
][i
]=-edge
[i
][j
];
read(q
);
for(int p
=1;p
<=q
;++p
)
{
read(k
);
for(int i
=1;i
<=k
;++i
) read(arr
[i
]);
cnt
=edge
[arr
[k
]][arr
[1]];
for(int i
=1;i
<k
;++i
) cnt
+=edge
[arr
[i
]][arr
[i
+1]];
printf("%d\n",abs(cnt
));
}
return 0;
}
