平面图转对偶图

方法：

1.分成正反两个单向边，每个边属于一个面

2.每个点按照极角序sort出边

3.枚举每一个边，这个边的nxt就是反边的前一个（这样找到的是面的边逆时针的）

4.相当有了置换，把每个nxt环找到，加上统一编号，并计算面积

5.有向面积为负数的是无限域，仅有一个

6.原来的单向边“旋转90度”，连接两个面

然后本题再跑一个以无限域为根的生成树

记录每个原来的边是否是生成树上的边

并记录生成树子树的S和S^2

询问：

如果当前的边是生成树边的话，如果属于的面作为儿子，加上S和S^2，否则减去

当面的边逆时针求出的，多边形也是逆时针给出的时候，显然是正确的

（画图理解）

注意新图的点数是2*n级别的。

 

#include
      
       #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define int long longusing namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
        
         il void output(T x){
     if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
     if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){
     for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int M=1200000+5;const int N=2e5+5;const double eps=1e-10;int n,m,q;struct po{    ll x,y;    po(){}    po(ll xx,ll yy){        x=xx;y=yy;    }    po friend operator -(po a,po b){        return po(a.x-b.x,a.y-b.y);    }    ll friend operator *(po a,po b){        return a.x*b.y-a.y*b.x;    }}p[N];struct edge{    int x,y,id;    double du;    bool friend operator <(edge a,edge b){        if(fabs(a.du-b.du)
           
            b return atan2(b.y-a.y,b.x-a.x);}vector
            
             to[N],b[M];void add(int x,int y){ e[++tot].x=x;e[tot].y=y; e[tot].du=atan2(p[y].y-p[x].y,p[y].x-p[x].x); e[tot].id=tot; to[x].push_back(e[tot]);}int cnt;ll S[M];int rt;int mem[M];void build(){ for(reg i=1;i<=n;++i) sort(to[i].begin(),to[i].end()); for(reg i=2;i<=tot;++i){ // edge now=(edge){e[i].y,e[i].x,i^1,an(p[e[i].y],p[e[i].x])}; auto it=lower_bound(to[e[i].y].begin(),to[e[i].y].end(),e[i^1]); if(it!=to[e[i].y].begin()) --it; else it=to[e[i].y].end(),--it; nxt[i]=(*it).id; } for(reg i=2;i<=tot;++i){ if(pos[i]) continue; pos[i]=pos[nxt[i]]=++cnt; for(reg j=nxt[i];e[j].y!=e[i].x;j=nxt[j],pos[j]=cnt){ S[cnt]+=(p[e[j].x]-p[e[i].x])*(p[e[j].y]-p[e[i].x]); } if(S[cnt]<=0) rt=cnt; } for(reg i=2;i<=tot;++i){ b[pos[i]].push_back((edge){pos[i],pos[i^1],i,0}); }}ll S2[M];int fa[M];bool vis[M];void dfs(int x){ // cout<<" xx "<
             
              <