HNOI 2016 矿区（对偶图）

发表于 |
字数统计: 1,919字 | 阅读时长 ≈ 9min

[Hnoi2016 day2]矿区

问题描述

平面上的矿区划分成了若干个开发区域。简单地说，你可以将矿区看成一张连通的平面图，平面图划分为了若干平面块，每个平面块即为一个开发区域，平面块之间的边界必定由若干整点(坐标值为整数的点)和连接这些整点的线段组成。每个开发区域的矿量与该开发区域的面积有关：具体而言，面积为s的开发区域的矿量为 s^2。

现在有 m 个开采计划。每个开采计划都指定了一个由若干开发区域组成的多边形，一个开采计划的优先度被规定为矿量的总和÷开发区域的面积和；例如，若某开采计划指定两个开发区域，面积分别为 a和b，则优先度为$\frac{a^2+b^2}{a+b}$。由于平面图是按照划分开发区域边界的点和边给出的，因此每个开采计划也只说明了其指定多边形的边界，并未详细指明是哪些开发区域（但很明显，只要给出了多边形的边界就可以求出是些开发区域）

你的任务是求出每个开采计划的优先度。为了避免精度问题，你的答案必须按照分数的格式输出，即求出分子和分母，且必须是最简形式（分子和分母都为整数，而且都消除了最大公约数；例如，若矿量总和是 1.5，面积和是2，那么分子应为3，分母应为4；又如，若矿量和是 2，面积和是 4，那么分子应为 1，分母应为 2）。由于某些原因，你必须依次对每个开采计划求解（即下一个开采计划会按一定格式加密，加密的方式与上一个开采计划的答案有关）。

输入格式

第一行三个正整数 n,m,k，分别描述平面图中的点和边，以及开采计划的个数。

接下来n行，第 i行(i=1,2,…,n)有两个整数$x_i, y_i$, 表示点i的坐标为$(x_i, y_i)$。

接下来m行，第 i行有两个正整数a,b，表示点a和b 之间有一条边。

接下来一行若干个整数，依次描述每个开采计划。每个开采计划的第一个数c指出该开采计划由开发区域组成的多边形边界上的点的个数为d=(c+P) mod n + 1；

接下来d个整数，按逆时针方向描述边界上的每一个点：设其中第i个数为z_i，则第i个点的编号为$(z_i+P) mod n + 1$。其中P 是上一个开采计划的答案中分子的值；对于第 1 个开采计划，P=0。

输出格式

对于每个开采计划，输出一行两个正整数，分别描述分子和分母。

样例输入

9 14 5

0 0

1 0

2 0

0 1

1 1

2 1

0 2

1 2

2 2

1 2

2 3

5 6

7 8

8 9

1 4

4 7

5 8

3 6

6 9

4 8

1 5

2 6

6 8

3 3 0 4 7 1 3 4 6 4 8 0 4 3 6 2 3 8 0 4 6 2 5 0 4 5 7 6 3

样例输出

1 1

1 2

1 1

9 10

3 4

提示

对于100%的数据，$n, k ≤ 2×10^5, m ≤ 3n-6, |x_i|, |y_i| ≤ 3×10^4$。所有开采计划的d之和不超过$2×10^6$。保证任何开采计划都包含至少一个开发区域，且这些开发区域构成一个连通块。保证所有开发区域的矿量和不超过 $2^{63}-1$。保证平面图中没有多余的点和边。保证数据合法。

本题显然考虑对偶图，然后就是平面图求对偶图的问题了。

求出对偶图后，在对偶图上以无穷域为根求一个DFS树，并统计每个点的子树矿量和与面积和，那么给每条边规定方向，令原图中的边对应上逆时针旋转$90$度后对偶图中的边，然后在原图中跑每一条边，如果该边的对应边是从DFS树上儿子走向父亲的，那么答案减去该儿子所在子树权值，否则就加上。

画个图就能发现，这是正确的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<unordered_map>
#define ll long long
#define N 200005
using namespace std;
char *p1,*p2,buf[1<<20];
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R()
{
	char t=GC;bool f=0;int x=0;
	while(t!='-'&&(t<48||t>57))t=GC;
	if(t=='-')f=1,t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<1)+(x<<3)+t-48;
	return f?-x:x;
}
int n,m,k,cnt=1,tot,rt;
int NE[N<<3],num[N<<3],q[N],fa[N<<1];
ll ans1,ans2,s[N<<1],s2[N<<1];
bool vis[N<<1],mark[N<<3];
struct node{ll x,y;}p[N];
node operator+(node a,node b){return (node){a.x+b.x,a.y+b.y};}
node operator-(node a,node b){return (node){a.x-b.x,a.y-b.y};}
ll operator*(node a,node b){return a.x*b.y-a.y*b.x;}
struct nodd
{
	int x,y,id;double alp;
	nodd(int tx=0,int ty=0,int tid=0)
	{
		x=tx;y=ty;id=tid;
		alp=atan2((double)(p[y].y-p[x].y),(double)(p[y].x-p[x].x));
	}
}e[N<<3];
bool operator<(nodd a,nodd b)
{return a.alp<b.alp;}
vector<nodd>E[N],G[N<<1];
int Find(int x,nodd tmp)
{return lower_bound(E[x].begin(),E[x].end(),tmp)-E[x].begin();}
ll gcd(ll x,ll y)
{return y?gcd(y,x%y):x;}
void Build()
{
	int i,j,tmp,st;ll area;
	for(i=2;i<=cnt;i++)
	if(!num[i])
	{
		area=0;tot++;
		j=i;st=e[i].x;
		do{
			num[j]=tot;
			area+=p[e[j].x]*p[e[j].y];
			j=NE[j];
		}while(j!=i);
		s[tot]=area;s2[tot]=area*area;
		if(area<=0)rt=tot;
	}
	for(i=2;i<=cnt;i++)G[num[i]].push_back(nodd(num[i],num[i^1],i));
}
void DFS(int x)
{
	int i,y;vis[x]=1;
	for(i=0;i<G[x].size();i++)
	{
		y=G[x][i].y;
		if(vis[y])continue;
		mark[G[x][i].id]=mark[G[x][i].id^1]=1;
		fa[y]=x;DFS(y);
		s[x]+=s[y];s2[x]+=s2[y];
	}
}
int main_main()
{
	int i,j,x,y,z;
	n=_R();m=_R();k=_R();
	for(i=1;i<=n;i++)p[i].x=_R(),p[i].y=_R();
	for(i=1;i<=m;i++)
	{
		x=_R();y=_R();
		cnt++;e[cnt]=nodd(x,y,cnt);E[x].push_back(e[cnt]);
		cnt++;e[cnt]=nodd(y,x,cnt);E[y].push_back(e[cnt]);
	}
	for(i=1;i<=n;i++)sort(E[i].begin(),E[i].end());
	for(i=2;i<=cnt;i++)
	{
		int tmp=Find(e[i].y,e[i^1])-1;
		if(tmp<0)tmp+=E[e[i].y].size();
		NE[i]=E[e[i].y][tmp].id;
	}
	Build();DFS(rt);
	for(i=1;i<=k;i++)
	{
		z=_R();z=(z+ans2)%n+1;
		for(j=1;j<=z;j++)
		{
			x=_R();
			q[j]=(x+ans2)%n+1;
		}
		ans1=ans2=0;q[z+1]=q[1];
		for(j=1;j<=z;j++)
		{
			x=q[j];y=q[j+1];int tmp=E[x][Find(x,nodd(x,y,0))].id;
			if(!mark[tmp])continue;
			if(num[tmp]==fa[num[tmp^1]])ans1-=s[num[tmp^1]],ans2-=s2[num[tmp^1]];
			else ans1+=s[num[tmp]],ans2+=s2[num[tmp]];
		}
		ll d=gcd(ans1,ans2);
		ans1/=d;ans2/=d;
		if(ans2&1)ans1<<=1;else ans2>>=1;
		printf("%lld %lld\n",ans2,ans1);
	}
}
const int main_stack=16;    
char my_stack[128<<20];    
int main() {    
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");    
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");    
  main_main();    
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");    
  return 0;    
}