传送门
题意
Cirno闲着无事的时候喜欢冰冻青蛙。 Cirno每次从雾之湖中固定的n个结点中选出一些点构成一个简单多边形，Cirno运用自己的能力能将此多边形内所有青蛙冰冻。 雾之湖生活着m只青蛙,青蛙有大有小，所以每只青蛙的价值为一个不大于10000的正整数。 Cirno很想知道每次冻住的青蛙的价值总和。因为智商有限，Cirno将这个问题交给完美算术教室里的你。 因为爱护动物，所以每次冻结的青蛙会被放生。也就是说一只青蛙可以被多次统计。
数据范围
对于30%的数据，n,m<=100; q<=100
对于60%的数据，n,m<=100; q<=10000
对于100%的数据，n,m<=1000; q<=10000
-10000<=x,y<=10000; 0< v<=10000
题解
首先得保证不存在三点共线。
先每个点极角排序，然后
n
2
n^{2}
n2求得所有点两两之间连线，和我们选定的原点(t[0])围成的三角形，记录三角形覆盖的价值和(如
t
[
i
]
t[i]
t[i]和
t
[
j
]
t[j]
t[j]的信息就记录在
f
[
i
]
[
j
]
f[i][j]
f[i][j]里，
f
[
i
]
[
j
]
f[i][j]
f[i][j],
f
[
j
]
[
i
]
f[j][i]
f[j][i]是等价的) 然而利用多边形计算面积，加上逆时针的三角形，减去顺时针的三角形，取个绝对值就好了。
upd. 梯形剖分： 按
y
y
y值升序排序，维护每个点对
(
i
,
j
)
(i,j)
(i,j)与
y
y
y轴围成梯形的价值和。
b
s
t
bst
bst中极角排序即可。
代码
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=2005;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,i,j,f[N][N],tag[N],b[N],p,Q,ans;
int rt,cnt,sz,sum[N],c[N],num[N],id[N],rs[N],ls[N],rnk[N];
struct P{
int x,y,v,id;
P(int x=0,int y=0,int v=0,int id=0):x(x),y(y),v(v),id(id) {}
}t[N];
inline int sqr(int x){return x*x;}
int operator *(P a,P b){return a.x*b.y-a.y*b.x;}
inline db dis(P a,P b){return sqr(a.x-b.x)+sqr(a.y-b.y);}
inline P sub(P a,P b){return P(a.x-b.x,a.y-b.y,0,0);}
inline int cal(P a,P b,P c){return sub(b,a)*sub(c,a);}
inline bool cmp(const P& a,const P& b){
return cal(t[0],a,b)==0? dis(t[0],a)<dis(t[0],b) : cal(a,b,t[0])>0 ;
}
inline void turn(int &k,int jud){
int t;
if(jud==1){t=ls[k];ls[k]=rs[t];rs[t]=k;}
else{t=rs[k];rs[k]=ls[t];ls[t]=k;}
sum[t]=sum[k];sum[k]=sum[ls[k]]+sum[rs[k]]+c[k];k=t;
}
inline void insert(int &k)
{
if(!k){
k=++cnt;
ls[k]=rs[k]=0;rnk[k]=rand();
sum[k]=c[k]=t[j].v;
num[k]=j;
}else{
sum[k]+=t[j].v;
if(cal(t[i],t[j],t[num[k]])>0){
insert(ls[k]);
if(rnk[ls[k]]<rnk[k]) turn(k,1);
}else{
insert(rs[k]);
sz+=sum[ls[k]]+c[k];
if(rnk[rs[k]]<rnk[k]) turn(k,0);
}
}
}
int main(){
n=read();m=read();
t[0].x=-12345,t[0].y=-15432;
for(i=1;i<=n;i++) t[i].x=read(),t[i].y=read(),t[i].id=i;
for(i=n+1;i<=n+m;i++) t[i].x=read(),t[i].y=read(),t[i].v=read(),t[i].id=i;
sort(t+1,t+m+n+1,cmp);
for(i=1;i<=n+m;i++) tag[t[i].id]=i;
for(i=1;i<n+m;i++){
rt=0,cnt=0;
for(j=i+1;j<=n+m;j++){
sz=0;
insert(rt);
f[i][j]=f[j][i]=sz;
}
}
Q=read();
while(Q--){
ans=0;
p=read();
for(i=1;i<=p;i++) b[i]=tag[read()];
b[p+1]=b[1];
for(i=1;i<=p;i++){
if(cal(t[0],t[b[i]],t[b[i+1]])>0) ans+=f[b[i]][b[i+1]];
else ans-=f[b[i]][b[i+1]];
}
if(ans<0) ans=-ans;
printf("%d\n",ans);
}
return 0;
}
