BZOJ 4541 【HNOI2016】 矿区

题目链接：矿区

　　这道题去年暑假就想写了，但是一直拖拉，以至于现在才来写这道题。以前一直在刻意回避几何类的题目，但到了现在这个时候，已经没有什么好害怕的了。

　　正巧今天神犇\(xzy\)讲了这道题，那我就去写吧。顺便给平面图转对偶图写个学习笔记。

　　我先讲一下平面图如何转对偶图吧(其实我早就知道了，一直懒得写)。

　　首先，对偶图最基本的需求就是把平面图中的每个块给抠出来。那么，我们该怎么抠呢？

　　我们显然可以将每一条无向边都变成两条有向边，这样的话围成每个块的边就不会重复且恰好把每条边用一次(最后剩下的边围出来的是无穷域)，因此我们就可以通过记录每条边是否被访问来判断是否抠出来了所有块。所以，我们用邻接表存边时就可以控制一下边的标号，使得边\(i\)和边\(i \ xor\ 1\)互为反向边。

　　因为我们要保证抠出来个块中没有边，所以我们肯定要沿着块的边缘一直顺时针走或者是逆时针走。我个人倾向于逆时针走(也就是每条有向边的左边是它对应的块)，因为这样的话，我们直接用叉积来算块的有向面积的话得到的将是一个正数，而无穷域算出来就会是负数。这样就可以非常方便地判断无穷域。

　　那么，假设我们现在正在边$i$上，那么我们下一步该往拿走呢？非常显然，我们把$i$反向，然后顺时针旋转，碰到的第一条边就是下一条我们要走的边。如此一路走下去，当我们碰到一条已经被访问过的边，那么我们就找出了一些首尾相连的边，也就是说抠出了一个块。我们把这个块标个号，然后记录这些边属于这个块即可。

　　所以，我们需要给每个点连出去的边排个序。这个可以使用系统自带的$atan2$函数，$atan2(y,x)$将返回向量$(x,y)$与$x$轴正方向的夹角，范围在$(-\pi,\pi]$中。我们可以在读入完所有的边之后，对于每个点，扫一遍所有的出边，然后按向量与$x$轴正方向的夹角大小排个序，记录一下每条边的顺时针方向第一条是什么(记得首尾相接连成一个环)。

　　最后，无穷域的判定有两种方式。一种是上文讲到的判有向面积的正负，还有一种就是在抠其它块之前，先把无穷域给抠出来，这样就不会影响到其它边了。具体做法可以从左下角的一个点(最左还是最下都可以)出发，先走夹角最大的一条边，这样抠出来的块就是无穷域。所以相比第二种，第一种其实更好写。

　　于是平面图转对偶图就这么愉快地解决啦！我们下面进入这道题。

　　题目要求的是面积的平方之和与面积之和的比，这和对偶图有什么关系啊！转完对偶图之后该怎么做呢？

　　我们考虑任取对偶图的一棵生成树，然后把无穷域提做根，然后我们来思考一下这棵树在平面图上代表着什么。我们在这棵树上$dfs$，实际上就是在各个块之间进进出出，并且会经过每一个块。于是，我们就可以只考虑这棵树上的边，而把其他的边给忽略掉。那么，当我们需要求平面图上一个多边形的面积时，我们显然可以顺着这个多边形的边走，如果发现这条边被选入了在我们构出的树上，那么我们可以在这条边由父亲指向孩子时减去子树内所有的块面积之和，有孩子指向父亲是再加回来。这样的话，最终得到的面积的绝对值就是这个多边形的面积之和。面积的平方同理。这里好像不好理解……如果不能理解的话建议画个图，然后就很清晰了。

　　似乎全是文字有点丑……不过我觉得讲的还是听清楚的(也许你不这么觉得)……

　　下面贴代码(代码丑了点)：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define mod 900007
#define maxn 200010
#define maxy 400010
#define maxm 1200010
#define point pair<int,int>
#define sx first
#define sy second

using namespace std;
typedef long long llg;

pair<double,int>a[maxm>>1];//排序使用
point po[maxn];//点
int n,m,k,rt,ff[maxy],fr[maxm],yu,fa[maxy];//rt表示无穷域,ff是并查集,fr表示每条边左边的域,yu表示抠出的域数
int h1[maxn],n1[maxm],t1[maxm],tt=1;//原图邻接表
int h2[maxy],n2[maxm],t2[maxm];//域的邻接表
int h3[mod],n3[maxm],t3[maxm],x3[maxm],y3[maxm],t_;//hash挂链
llg siz[maxy],sizs[maxy],P,Q,np,nq;//P为分子,Q为分母
bool vis[maxm];

int getint(){
    int w=0;bool q=0;
    char c=getchar();
    while((c>'9'||c<'0')&&c!='-') c=getchar();
    if(c=='-') c=getchar(),q=1;
    while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
    return q?-w:w;
}

int find(int x){return ff[ff[x]]==ff[x]?ff[x]:ff[x]=find(ff[x]);}
int cha(point a,point b){return a.sx*b.sy-a.sy*b.sx;}//向量叉积
void link(int x,int y){
    t1[++tt]=y;n1[tt]=h1[x];h1[x]=tt;
    t1[++tt]=x;n1[tt]=h1[y];h1[y]=tt;
}

void dfs(int u,int fe){
    fa[u]=fe;
    for(int i=h2[u],v;v=t2[i],i;i=n2[i])
        if(v!=fe) dfs(v,u),siz[u]+=siz[v],sizs[u]+=sizs[v];
}

void jia(int x,int y,int i){
    llg now=(llg)(x-1)*yu+(llg)y-1;
    y3[++t_]=y; x3[t_]=x; t3[t_]=i;
    n3[t_]=h3[now%mod]; h3[now%mod]=t_;
}

int find(int x,int y){//寻找连接点x,y的边的编号
    int u=((llg)(x-1)*yu+(llg)y-1)%mod;
    for(int i=h3[u];i;i=n3[i])
        if(x3[i]==x && y3[i]==y) return t3[i];
    return 0;
}

llg gcd(llg x,llg y){
    llg r=x%y;
    while(r) x=y,y=r,r=x%y;
    return y;
}

int main(){
    File("mine");
    n=getint(); m=getint(); k=getint();
    for(int i=1,x,y;i<=n;i++){
        x=getint();y=getint();
        po[i]=make_pair(x,y);
    }
    for(int i=1;i<=m;i++) link(getint(),getint());
    tt=0;
    for(int u=1,d=0;u<=n;u++,d=0){//给所有边极角排序
        for(int i=h1[u],v;v=t1[i],i;i=n1[i])
            a[++d]=make_pair(atan2(po[v].sy-po[u].sy,po[v].sx-po[u].sx),i);
        sort(a+1,a+d+1); n1[a[1].sy]=a[d].sy;
        for(int i=2;i<=d;i++) n1[a[i].sy]=a[i-1].sy;
    }
    for(int l=2,o=1,u,v;l<=m*2+1;l++)//抠出所有域
        if(!vis[l]){
            yu++; ff[yu]=yu;
            v=t1[l]; o=n1[l^1];
            while(!vis[o]){
                u=v,v=t1[o]; fr[o]=yu;
                vis[o]=1; o=n1[o^1];
                siz[yu]+=cha(po[u],po[v]);
            }
            if(siz[yu]<0) rt=yu;
            sizs[yu]=siz[yu]*siz[yu];
        }
    for(int i=2,x,y;vis[i];i+=2)//随便构棵生成树
        if(find(fr[i])!=find(fr[i^1])){
            x=fr[i]; y=fr[i^1];//x,y是两个相邻的域
            jia(t1[i],t1[i^1],i^1),jia(t1[i^1],t1[i],i);
            t2[++tt]=y;n2[tt]=h2[x];h2[x]=tt;
            t2[++tt]=x;n2[tt]=h2[y];h2[y]=tt;
            ff[find(x)]=find(y);
        }
    dfs(rt,0);
    while(k--){
        int c=(getint()+P)%n+1,fi,u,v,x;
        fi=v=(getint()+P)%n+1; np=nq=0;
        for(int i=2;i<=c;i++){
            u=v,v=(getint()+P)%n+1;
            if(!(x=find(u,v))) continue;
            if(fa[fr[x]]==fr[x^1]) np+=sizs[fr[x]],nq+=siz[fr[x]];
            else np-=sizs[fr[x^1]],nq-=siz[fr[x^1]];
        }
        if((x=find(v,fi))){
            if(fa[fr[x]]==fr[x^1]) np+=sizs[fr[x]],nq+=siz[fr[x]];
            else np-=sizs[fr[x^1]],nq-=siz[fr[x^1]];
        }
        P=abs(np); Q=abs(nq<<1); llg _g=gcd(P,Q);//由于我叉积算面积没有除以2,所以最终最给分母乘2
        P/=_g; Q/=_g; printf("%lld %lld\n",P,Q);
    }
    return 0;
}