大概的思路就是平面图转对偶图,然后平面当点建树,记录面积和面积的平方的子树和,利用一些性质求解。

这道题的难点就在于

  1. 把已有的点,选择一些边,化成一个个独立的平面(有可能不封闭)。
  2. 由于询问给定的是边界,如何判定边界中含有多少个独立平面。

对于第一个难点,可以采用平面图转对偶图的形式来实现,即定起点,进行极角排序。

找出一条边的后继边,划分平面。

不难发现,如果是双向边,若平面接壤,恰好是各占一条。

同时求平面面积,如果面积为负,则说明这个平面不封闭,由于在询问中不会产生贡献,可以把其当成树的根。

建树的时候,记录一下树边(即遍历到的的双向边),面积和面积的平方的子树和,这个在询问时起到很大的作用。

如图

20.PNG

这个树建出来是一条链($1->2->3->4->5$)。

若询问要求$3,4$平面,那么也就是做一个容斥,$3$子树减去$5$子树即可。

由于边界上,一定含有一条树边连接$3$与$3$的父亲$2$,即红色的$BI$,以及$5$与$5$的父亲$4$,即红色的$DE$。

那么就可以利用这个性质,推广一下:如果在边界上碰到一条树边,判断一下这条边的方向(是由父亲指向儿子,还是儿子指向父亲)之后对贡献取一下正负就可以做到容斥。

其实这个方向没有太大必要,取个绝对值是一样的。

还有一个小技巧,由于面积可能出现$.5$的情况,乘下$2$就好了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<vector>
#include<algorithm>
#define gc getchar()
#define ll long long
#define eps 1e-8
#define ld long double 
#define ull unsigned long long
using namespace std;
const int N=2e5+5,M=12e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int n,m,q;
struct node
{
    ll x,y;
    node(int x=0,int y=0):x(x),y(y){}
    node operator +(const node a)const{return node(x+a.x,y+a.y);}
    node operator -(const node a)const{return node(x-a.x,y-a.y);}
}a[N];
inline ll cross(node p1,node p2){return p1.x*p2.y-p1.y*p2.x;}
struct edge
{
    int id,x,y;double ang;
    edge(int id=0,ll x=0,ll y=0,double ang=0.0):id(id),x(x),y(y),ang(ang){}
    bool operator <(const edge a)const{return fabs(ang-a.ang)<eps?y<a.y:ang<a.ang;}
}e[M];int len,pos[M],num,root,f[M],b[N],nxt[M];
vector<edge>vec[N];
vector<int>ed[M],ps[M];
ll s1[M],s2[M];bool v[M],ms[M];
void add(int x,int y)
{
    ++len;e[len]=edge(len,x,y,atan2(a[y].y-a[x].y,a[y].x-a[x].x));
    vec[x].push_back(e[len]);
}
void build()
{
    for(int i=1;i<=n;i++)sort(vec[i].begin(),vec[i].end());
    for(int i=2;i<=len;i++)
    {
        int id=e[i].y;
        vector<edge>::iterator it=lower_bound(vec[id].begin(),vec[id].end(),e[i^1]);
        if(it==vec[id].begin())it=vec[id].end();
        --it;nxt[i]=it->id;
    }
    for(int i=2;i<=len;i++)
    {
        if(pos[i])continue;
        pos[i]=pos[nxt[i]]=++num;
        for(int k=nxt[i];e[k].y!=e[i].x;k=nxt[k],pos[k]=num)
            s1[num]+=cross(a[e[k].x]-a[e[i].x],a[e[k].y]-a[e[i].x]);
        if(s1[num]<=0)root=num,s1[num]=0;
    }
    for(int i=2;i<=len;i++)ed[pos[i]].push_back(pos[i^1]),ps[pos[i]].push_back(i);    
}
void dfs(int x)
{
    s2[x]=s1[x]*s1[x];s1[x]<<=1;v[x]=1;
    for(int i=0,siz=ed[x].size();i<siz;i++)
    {
        int y=ed[x][i],tg=ps[x][i];
        if(v[y])continue;
        f[y]=x;ms[tg]=ms[tg^1]=1;
        dfs(y);
        s2[x]+=s2[y];s1[x]+=s1[y];
    }
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void solve()
{
    ll ans1=0,ans2=0;
    while(q--)
    {
        int x;qr(x);x=(x+ans1)%n+1;
        for(int i=1;i<=x;i++)qr(b[i]),b[i]=(b[i]+ans1)%n+1;
        b[x+1]=b[1];
        ans1=ans2=0;
        for(int i=1;i<=x;i++)
        {
            int p1=b[i],p2=b[i+1];
            edge z=edge(0,p1,p2,atan2(a[p2].y-a[p1].y,a[p2].x-a[p1].x));
            vector<edge>::iterator it=lower_bound(vec[p1].begin(),vec[p1].end(),z);
            int j=it->id;
            if(!ms[j])continue;
            if(f[pos[j]]==pos[j^1])ans1+=s2[pos[j]],ans2+=s1[pos[j]];
            else ans1-=s2[pos[j^1]],ans2-=s1[pos[j^1]];
        }
        ll d=gcd(ans1,ans2);
        ans1/=d,ans2/=d;
        qw(ans1),putchar(' '),qw(ans2),puts("");
    }
}
int main()
{
    //freopen("mine2.in","r",stdin);
//    freopen("mine2.ans","w",stdout);
    qr(n),qr(m),qr(q);
    int x,y;len=1;
    for(int i=1;i<=n;i++)
    {
        qr(x),qr(y);
        a[i]=node(x,y);
    }
    for(int i=1;i<=m;i++)
    {
        qr(x),qr(y);
        add(x,y),add(y,x);
    }
    build();
    dfs(root);
    solve();
    return 0;
}