题目大意
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+m个结点，保证不存在三点共线情况。
题解
读入优化没读负号居然只挂了40
若干种做法
第一种：
按照求多边形面积的做法，先移到第一象限，然后求OAB里面点的权值和
把线段变成直线分成七块，转为求一个点+一段夹角区间内的点，排序统计
第二种：
把第一种的求法变一下，延长AB交x轴与C，求OAC-OBC，枚举一个点以及一条射线统计
第三种：
求面积的时候求线段往下投影形成的梯形面积，计算这里面的权值
枚举一个点以及一条射线，分左右讨论，在梯形里面的一定是斜率在射线前并且x在一定范围，排序+线段树
虽然没有三点共线但是还是会有两个点在同一条垂线上，把所有点旋转1°即可
code
第一种
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define abs(x) ((x)>0?(x):-(x))
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define E 0.0000001
//#define file
using namespace std;
struct type{int x,y,s;} b[1001],c[1001];
struct Type{double S;int s;} a[2001];
int f1[1001][1001],f2[1001][1001],f3[1001][1001],d[1001],n,m,Q,i,j,k,l,tot,mn1,mn2,Sum,sum,ans;
double S;
char ch;
void Read(int &x) {int k=1;x=0; ch=getchar(); while (ch<'0' || ch>'9') k=(ch=='-')?-1:k,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+(ch-'0'),ch=getchar();x*=k;}
bool cmp(Type a,Type b) {return a.S<b.S;}
ll cj(type a,type b) {return b.x*a.y-a.x*b.y;}
double js(type a)
{
if (abs(a.y)<=E)
{
if (a.x>0) return 0;
else return M_PI;
}
if (abs(a.x)<=E)
{
if (a.y>0) return M_PI/2;
else return M_PI*3/2;
}
if (a.y>0) return atan2(a.y,a.x);
else return atan2(a.y,a.x)+M_PI*2;
}
double turn(double s)
{
if (s<0) s+=M_PI*2;
if (s>M_PI*2) s-=M_PI*2;
return s;
}
void work1()
{
tot=0;
fo(i,1,n) a[++tot]={js(b[i]),-i};
fo(i,1,m) a[++tot]={js(c[i]),c[i].s};
sort(a+1,a+tot+1,cmp);
fo(i,1,tot)
if (a[i].s<0)
{
sum=0;
fd(j,i,1)
if (a[j].s<0)
f1[-a[i].s][-a[j].s]=f1[-a[j].s][-a[i].s]=sum;
else
sum+=a[j].s;
}
}
void work2()
{
fo(i,1,n)
{
S=js({-b[i].x,-b[i].y});
tot=0;
fo(j,1,n)
if (i!=j) a[++tot]={js({b[j].x-b[i].x,b[j].y-b[i].y}),-j};
fo(j,1,m) a[++tot]={js({c[j].x-b[i].x,c[j].y-b[i].y}),c[j].s};
fo(j,1,tot) a[j].S=turn(a[j].S-S);
sort(a+1,a+tot+1,cmp);
sum=0;
fo(j,1,tot)
if (a[j].S<=M_PI)
{
if (a[j].s<0)
f2[i][-a[j].s]=(abs(a[j].S-M_PI)<E)?0:sum;
else
sum+=a[j].s;
}
else break;
k=j,sum=0;
fd(j,tot,k)
{
if (a[j].s<0)
f2[i][-a[j].s]=(abs(a[j].S-M_PI)<E)?0:sum;
else
sum+=a[j].s;
}
}
}
void work3()
{
fo(i,1,n)
{
S=js({b[i].x,b[i].y});
tot=0;
fo(j,1,n)
if (i!=j) a[++tot]={js({b[i].x-b[j].x,b[i].y-b[j].y}),-j};
fo(j,1,m) a[++tot]={js({c[j].x-b[i].x,c[j].y-b[i].y}),c[j].s};
fo(j,1,tot) a[j].S=turn(a[j].S-S);
sort(a+1,a+tot+1,cmp);
sum=0;
fo(j,1,tot)
if (a[j].S<=M_PI)
{
if (a[j].s<0)
f3[i][-a[j].s]=(abs(a[j].S-M_PI)<E)?0:sum;
else
sum+=a[j].s;
}
else break;
k=j,sum=0;
fd(j,tot,k)
{
if (a[j].s<0)
f3[i][-a[j].s]=(abs(a[j].S-M_PI)<E)?0:sum;
else
sum+=a[j].s;
}
}
}
int Js(int x,int y)
{
int s=cj(b[x],b[y]);
if (!s) return 0;
else return (f1[x][y]+f2[x][y]+f3[x][y]+f2[y][x]+f3[y][x]-Sum)*((s>0)?1:-1);
}
int main()
{
#ifdef file
freopen("a.in","r",stdin);
#endif
Read(n),Read(m),mn1=mn2=2147483647;
fo(i,1,n) Read(b[i].x),Read(b[i].y),mn1=min(mn1,b[i].x),mn2=min(mn2,b[i].y);
fo(i,1,m) Read(c[i].x),Read(c[i].y),Read(c[i].s),Sum+=c[i].s,mn1=min(mn1,c[i].x),mn2=min(mn2,c[i].y);
--mn1,--mn2;
fo(i,1,n) b[i].x-=mn1,b[i].y-=mn2;
fo(i,1,m) c[i].x-=mn1,c[i].y-=mn2;
work1();
work2();
work3();
Read(Q);
for (;Q;--Q)
{
Read(l);
fo(i,1,l) Read(d[i]);
ans=0;
fo(i,1,l-1) ans+=Js(d[i],d[i+1]);ans+=Js(d[l],d[1]);
ans=abs(ans);
printf("%d
",ans/2);
}
fclose(stdin);
fclose(stdout);
return 0;
}