1 条题解
-
1
#include<bits/stdc++.h> using namespace std; int read() { int q=0,w=1;char ch=' '; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar(); return q*w; } typedef long long LL; typedef double db; const int N=200005,M=1200005;const db eps=1e-10; #define RI register int int n,m,Q,tot=1,cnt,rt;LL ans1,ans2; struct point{int x,y;}p[N]; point operator - (point a,point b) {return (point){a.x-b.x,a.y-b.y};} LL operator * (point a,point b) {return 1LL*a.x*b.y-1LL*a.y*b.x;} struct edge{int id,u,v;db jd;}e[M]; bool operator < (edge a,edge b) {return fabs(a.jd-b.jd)<eps?a.v<b.v:a.jd<b.jd;} int nxt[M],pos[M],f[M],vis[M],istr[M],ask[M];LL s[M],ss[M]; vector<edge> h[N],tr[M]; void link(int x,int y) { ++tot,e[tot]=(edge){tot,x,y,atan2(p[y].y-p[x].y,p[y].x-p[x].x)}; h[x].push_back(e[tot]); } void build() { for(RI i=1;i<=n;++i) sort(h[i].begin(),h[i].end()); for(RI i=2;i<=tot;++i) { int v=e[i].v; vector<edge>::iterator kl=lower_bound(h[v].begin(),h[v].end(),e[i^1]); if(kl==h[v].begin()) kl=h[v].end();//其前一条就是最后一条 --kl,nxt[i]=(*kl).id; } for(RI i=2;i<=tot;++i) { if(pos[i]) continue; pos[i]=pos[nxt[i]]=++cnt; for(RI j=nxt[i];e[j].v!=e[i].u;j=nxt[j],pos[j]=cnt) s[cnt]+=(p[e[j].u]-p[e[i].u])*(p[e[j].v]-p[e[i].u]);//计算面积 if(s[cnt]<=0) rt=cnt;//无穷域 } for(RI i=2;i<=tot;++i) tr[pos[i]].push_back((edge){i,pos[i],pos[i^1]}); } void dfs(int x,int las) {//生成树 f[x]=las,ss[x]=1LL*s[x]*s[x],s[x]<<=1,vis[x]=1; //叉积算面积后应该除以2,但是为了避免小数,所以分子分母同时乘4 for(RI i=0,sz=tr[x].size();i<sz;++i) { int v=tr[x][i].v; if(vis[v]) continue; istr[tr[x][i].id]=istr[tr[x][i].id^1]=1,dfs(v,x); s[x]+=s[v],ss[x]+=ss[v]; } } LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;} void work() { while(Q--) { int js=(read()+ans1)%n+1; for(RI i=1;i<=js;++i) ask[i]=(read()+ans1)%n+1; ask[js+1]=ask[1],ans1=ans2=0; for(RI i=1;i<=js;++i) { int x=ask[i],y=ask[i+1]; edge ke=(edge){0,x,y,atan2(p[y].y-p[x].y,p[y].x-p[x].x)}; vector<edge>::iterator kl=lower_bound(h[x].begin(),h[x].end(),ke);//找边 int j=(*kl).id; if(!istr[j]) continue;//该边所在区域,是儿子就加是父亲就减 if(f[pos[j]]==pos[j^1]) ans1+=ss[pos[j]],ans2+=s[pos[j]]; else ans1-=ss[pos[j^1]],ans2-=s[pos[j^1]]; } LL tmp=gcd(ans1,ans2); ans1/=tmp,ans2/=tmp; printf("%lld %lld\n",ans1,ans2); } } int main() { int x,y; n=read(),m=read(),Q=read(); for(RI i=1;i<=n;++i) p[i]=(point){read(),read()}; for(RI i=1;i<=m;++i) x=read(),y=read(),link(x,y),link(y,x); build(),dfs(rt,0),work(); return 0; }
- 1
信息
- ID
- 220
- 时间
- 3000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者