题意
Cirno闲着无事的时候喜欢冰冻青蛙。
Cirno每次从雾之湖中固定的n个结点中选出一些点构成一个简单多边形，Cirno运用自己的能力能将此多边形内所有青蛙冰冻。
雾之湖生活着m只青蛙,青蛙有大有小，所以每只青蛙的价值为一个不大于10000的正整数。
Cirno很想知道每次冻住的青蛙的价值总和。因为智商有限，Cirno将这个问题交给完美算术教室里的你。
因为爱护动物，所以每次冻结的青蛙会被放生。也就是说一只青蛙可以被多次统计。
(n,m<=1000; q<=10000)
(-10000<=x,y<=10000; 0<v<=10000)
分析
参照xjr_01的题解。
首先介绍一个新东西：三角剖分。拿此题为例，我们把两类点混成一类，只是第一类点权值为 0。接下来，给所有点按照极角坐标排序，那么我们需要维护一个 tot[i][j] 表示原点、i、j 这三个点所构成的三角形包含的点的权值和，并且规定：i 到 j 是极角排序正方向时 tot[i][j] 为正（注意所有权值 v > 0），反之为负。那么在询问时对于一个简单多边形直接把相邻两个顶点的 tot 值累加起来即可。
至于如何维护 tot[i][j]，可以先确定 i 并以点 i 作为新的原点，然后按极角的顺序一个一个往平衡树内加点，每次加点 j 时统计一下当前平衡树内以 i 为原点且在向量 i->j 左的向量有多少个，这个个数就是 tot[i][j]。
用算多边形面积的方式来算权值……出题人真是个天才。我才知道这个算面积的方法叫“三角剖分”。
时间复杂度(O(n^2 log n + m*s))
代码
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read()
{
rg T data=0;
rg int w=1;
rg char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
{
data=data*10+ch-'0';
ch=getchar();
}
return data*w;
}
template<class T>il T read(rg T&x)
{
return x=read<T>();
}
typedef long long ll;
struct Vector
{
int x,y;
Vector(int x=0,int y=0):x(x),y(y){}
bool operator<(co Vector&v)co
{
return x*v.y-y*v.x?x*v.y-y*v.x<0:x*x+y*y>v.x*v.x+v.y*v.y;
}
Vector operator-(co Vector&v)co
{
return Vector(x-v.x,y-v.y);
}
}st(-10001,-10001);
co int N=2001;
int n,m;
struct Point
{
Vector v;
int val,id;
Point(Vector v=0,int val=0,int id=0):v(v),val(val),id(id){}
bool operator<(co Point&p)co
{
return v-st<p.v-st;
}
}ps[N];
int cp;
int root,tot;
Vector org;
namespace T
{
int ch[N][2],siz[N],pri[N];
Vector v[N];
int val[N],sum[N];
int newnode(co Point&p)
{
int x=++tot;
ch[x][0]=ch[x][1]=0,siz[x]=1,pri[x]=rand();
T::v[x]=p.v;
val[x]=sum[x]=p.val;
return x;
}
void pushup(int x)
{
siz[x]=siz[ch[x][0]]+1+siz[ch[x][1]];
sum[x]=sum[ch[x][0]]+val[x]+sum[ch[x][1]];
}
void split(int x,co Vector&v,int&l,int&r)
{
if(!x)
{
l=r=0;
return;
}
if(T::v[x]-org<v-org)
{
l=x;
split(ch[l][1],v,ch[l][1],r);
pushup(l);
}
else
{
r=x;
split(ch[r][0],v,l,ch[r][0]);
pushup(r);
}
}
int merge(int x,int y)
{
if(!x||!y)
return x+y;
if(pri[x]>pri[y])
{
ch[x][1]=merge(ch[x][1],y);
pushup(x);
return x;
}
else
{
ch[y][0]=merge(x,ch[y][0]);
pushup(y);
return y;
}
}
int insert(int&t,co Point&p)
{
int l,r;
split(t,p.v,l,r);
int ans=sum[l];
t=merge(l,merge(newnode(p),r));
return ans;
}
}
int pid[N],area[N][N];
void init()
{
std::sort(ps+1,ps+cp+1);
std::reverse(ps+1,ps+cp+1);
for(int i=1;i<=cp;++i)
if(ps[i].id<=n)
pid[ps[i].id]=i;
for(int i=1;i<=cp;++i)
{
root=tot=0;
org=ps[i].v;
for(int j=i;j<=cp;++j)
{
area[i][j]=T::insert(root,ps[j]);
if(i!=j)
area[j][i]=-area[i][j];
}
}
}
int rps[N];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m);
for(int i=1;i<=n;++i)
{
int x,y;
read(x),read(y);
ps[i]=Point(Vector(x,y),0,i);
}
for(int i=1;i<=m;++i)
{
int x,y,v;
read(x),read(y),read(v);
ps[n+i]=Point(Vector(x,y),v,n+i);
}
cp=n+m;
init();
int q;
read(q);
while(q--)
{
int s;
read(s);
for(int i=0;i<s;++i)
rps[i]=pid[read<int>()];
int ans=0;
for(int i=0;i<s;++i)
ans+=area[rps[i]][rps[(i+1)%s]];
printf("%d
",abs(ans));
}
return 0;
}