Cirno闲着无事的时候喜欢冰冻青蛙。
Cirno每次从雾之湖中固定的n个结点中选出一些点构成一个简单多边形，Cirno运用自己的能力能将此多边形内所有青蛙冰冻。
雾之湖生活着m只青蛙,青蛙有大有小，所以每只青蛙的价值为一个不大于10000的正整数。
Cirno很想知道每次冻住的青蛙的价值总和。因为智商有限，Cirno将这个问题交给完美算术教室里的你。
因为爱护动物，所以每次冻结的青蛙会被放生。也就是说一只青蛙可以被多次统计。
这道题是一道计算几何的基础题，适合最近在练习计算几何的我。
遇到这种类型的问题，其实很容易解决，我们给每条边定一个方向，设其为从横坐标较小的点到较大的点。
对于正方向的边，这条边下方的所有的权值按正的算，负方向的点，这条边下方的所有的权值按负的算。
对于一个点，我们可以将所有点分成在左侧和在右侧两部分，按斜率排序，从低到高，依次加入线段树统计答案。
这题一开始被卡了时间，要注意斜率要提前处理，可以快很多。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define N 3000 #define db double #define mxp 10000 #pragma GCC optimize(3) using namespace std; int n,m,q,s,g[N],i,j,ans,sum,temp,f[mxp*10],tp[N][N],x,y,bz[N]; db kp; struct node{ int x,y,val,id; db kp; }p1[N],p2[N]; db xp1=atan2(0,-1),xp2=atan2(-1,0),xp3=atan2(1,0); 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<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline db Abs(db x){ if (x<0) return -x; return x; } inline int cmp(node a,node b){ if (a.kp!=b.kp) return a.kp<b.kp; return a.x<b.x; } inline void insert(int x,int l,int r,int k,int p){ if (l==r){ f[x]+=p; return; } int mid=(l+r)/2; if (k<=mid) insert(x*2,l,mid,k,p); else insert(x*2+1,mid+1,r,k,p); f[x]=f[x*2]+f[x*2+1]; } inline int getsum(int x,int l,int r,int l1,int r1){ if (l1>r1) return 0; if (l1<=l&&r1>=r) return f[x]; int mid=(l+r)/2,sum=0; if (l1<=mid) sum+=getsum(x*2,l,mid,l1,r1); if (r1>mid) sum+=getsum(x*2+1,mid+1,r,l1,r1); return sum; } int main(){ n=read();m=read(); for (i=1;i<=n;i++) p1[i].x=read(),p1[i].y=read(),p1[i].id=i,p1[i].x+=mxp; for (i=1;i<=m;i++) p1[i+n].x=read(),p1[i+n].y=read(),p1[i+n].val=read(),p1[i+n].id=i,p1[i+n].x+=mxp; for (i=1;i<=n+m;i++) p2[i]=p1[i]; for (i=1;i<=n;i++){ x=p1[i].x,y=p1[i].y; for (j=1;j<=n+m;j++){ p2[j].kp=atan2(p2[j].y-y,p2[j].x-x); kp=p2[j].kp; p2[j].kp=Abs(p2[j].kp-xp2); if (kp<xp1&&kp>xp3) p2[j].kp=2*Abs(xp1-xp2)-p2[j].kp; } sort(p2+1,p2+n+m+1,cmp); for (j=1;j<=n+m;j++) if (p2[j].id!=i||p2[j].val>0){ if (p2[j].val){ if (p1[i].x<=p2[j].x) insert(1,0,mxp*2,p2[j].x,p2[j].val); else insert(1,0,mxp*2,p2[j].x,-p2[j].val); } else{ if (p1[i].x<=p2[j].x) tp[i][p2[j].id]=getsum(1,0,mxp*2,p1[i].x,p2[j].x-1); else tp[i][p2[j].id]=getsum(1,0,mxp*2,p2[j].x,p1[i].x-1); } } for (j=1;j<=n+m;j++) if (p2[j].val>0){ if (p1[i].x<=p2[j].x) insert(1,0,mxp*2,p2[j].x,-p2[j].val); else insert(1,0,mxp*2,p2[j].x,p2[j].val); } } q=read(); while (q--){ s=read(); for (i=1;i<=s;i++) g[i]=read(); g[++s]=g[1]; ans=0; for (i=1;i<s;i++) ans+=tp[g[i]][g[i+1]]; if (ans<0) ans=-ans; printf("%d ",ans); } return 0; }