http://www.lydsy.com/JudgeOnline/problem.php?id=4541 (题目链接)
题意
给出一个平面图，若干询问，每次询问一个凸多边形内小多边形面积的平方和与面积的和的比值。
Solution
*的神题，右转题解→_→：http://blog.****.net/philipsweng/article/details/51201092
细节
注意数组大小
代码
// bzoj4541
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf (1ll<<60)
#define HAS 40007
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
inline int gi() {
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*10+ch-'0';ch=getchar();}
return x*f;
} const int maxn=200010,maxm=600010;
int head[maxm],last[maxn],next[maxm<<1],par[maxm],fa[maxm],N,n,m,q,s,cnt=1,ccc;
LL area[maxm],AREA[maxm],sum[maxm],SUM[maxm],P,Q;
struct point {int x,y;}a[maxn];
struct chain {LL w;int id,next;}line[maxm<<1];
struct edge {int u,v,next,id;}e[maxm<<1],d[maxm<<1];
vector<pair<double,int> >V[maxn]; inline LL gcd(LL a,LL b) {return b==0 ? a : gcd(b,a%b);}
inline int find(int x) {return fa[x]==x ? x : fa[x]=find(fa[x]);}
inline int cross(point a,point b) {return a.x*b.y-b.x*a.y;} inline void link(edge *e,int u,int v) {
e[++cnt]=(edge){u,v,head[u],0};head[u]=cnt;
e[++cnt]=(edge){v,u,head[v],0};head[v]=cnt;
}
inline void build(int x) {
for (int i=x;!d[i].id;i=next[i]) {
d[i].id=N;
int tmp=-cross(a[d[i].u],a[d[i].v]);
area[N]+=tmp;
}
}
inline void dfs(int x) {
sum[x]=area[x];SUM[x]=AREA[x];
for (int i=head[x];i;i=e[i].next) if (e[i].v!=par[x]) {
par[e[i].v]=x;
dfs(e[i].v);
sum[x]+=sum[e[i].v];SUM[x]+=SUM[e[i].v];
}
}
inline int edgeid(int u,int v) {
LL tmp=(LL)u*n+(LL)v-1;
int id=tmp%HAS;
for (int i=last[id];i;i=line[i].next)
if (line[i].w==tmp) return line[i].id;
}
int main() {
n=gi(),m=gi(),q=gi(),s=1;
for (int i=1;i<=n;++i) {
a[i].x=gi(),a[i].y=gi();
if (a[i].x<a[s].x || (a[i].x==a[s].x && a[i].y<a[s].y)) s=i;
}
for (int u,v,i=1;i<=m;++i) u=gi(),v=gi(),link(d,u,v);
for (int i=1;i<=n;++i) { //以i为起点的边极角排序
for (int j=head[i];j;j=d[j].next)
V[i].push_back(make_pair(atan2(a[d[j].v].y-a[i].y,a[d[j].v].x-a[i].x),j));
sort(V[i].begin(),V[i].end());
for (int j=0,k=V[i].size();j<k;++j) next[V[i][j].second^1]=V[i][(j+1)%k].second; //next[x]表示走完边x后该走的边
}
N=1;build(V[s][0].second);area[1]=AREA[1]=0; //先抠无穷域，面积赋为0
for (int i=2;i<=cnt;++i) if (!d[i].id) {++N;build(i);AREA[N]=area[N]*area[N],area[N]<<=1;}
for (int i=2;i<=cnt;++i) { //hash
LL tmp=(LL)d[i].u*n+(LL)d[i].v-1;
int id=tmp%HAS;
line[++ccc]=(chain){tmp,i,last[id]};last[id]=ccc;
}
memset(head,0,sizeof(head));
for (int i=1;i<=N;++i) fa[i]=i;
int tmp=cnt;cnt=0;
for (int i=2;i<=tmp;i+=2) { //随意构一棵域之间的生成树
int u=d[i].id,v=d[i^1].id;
int r1=find(u),r2=find(v);
if (r1!=r2) fa[r1]=r2,link(e,u,v),d[i].next=d[i^1].next=-1;
}
dfs(1); //dfs统计一下子树权值和以及父亲关系
while (q--) {
LL tmp=P,c=(gi()+tmp)%n+1;
s=(gi()+tmp)%n+1;
P=0,Q=0;
for (int u,v=s,i=1;i<=c;++i) {
u=v,v=i==c ? s : (gi()+tmp)%n+1;
int t=edgeid(u,v);
if (d[t].next!=-1) continue;
int x=d[t].id,y=d[t^1].id;
if (par[x]==y) P-=SUM[x],Q-=sum[x];
else if (par[y]==x) P+=SUM[y],Q+=sum[y];
}
LL G=gcd(P,Q);
P/=G,Q/=G;
printf("%lld %lld\n",P,Q);
}
return 0;
}