題目連結
bzoj4541
題目描述
Description
平面上的礦區劃分成了若幹個開發區域。簡單地說，你可以将礦區看成一張連通的平面圖，平面圖劃分為了若幹平面塊，每個平面塊即為一個開發區域，平面塊之間的邊界必定由若幹整點(坐标值為整數的點)和連接配接這些整點的線段組成。每個開發區域的礦量與該開發區域的面積有關：具體而言，面積為s的開發區域的礦量為 s^2。現在有 m 個開采計劃。每個開采計劃都指定了一個由若幹開發區域組成的多邊形，一個開采計劃的優先度被規定為礦量的總和÷開發區域的面積和；例如，若某開采計劃指定兩個開發區域，面積分别為 a和b，則優先度為(a^2+b^2)/(a+b)。由于平面圖是按照劃分開發區域邊界的點和邊給出的，是以每個開采計劃也隻說明了其指定多邊形的邊界，并未詳細指明是哪些開發區域（但很明顯，隻要給出了多邊形的邊界就可以求出是些開發區域）。你的任務是求出每個開采計劃的優先度。為了避免精度問題，你的答案必須按照分數的格式輸出，即求出分子和分母，且必須是最簡形式（分子和分母都為整數，而且都消除了最大公約數；例如，若礦量總和是 1.5，面積和是2，那麼分子應為3，分母應為4；又如，若礦量和是 2，面積和是 4，那麼分子應為 1，分母應為 2）。由于某些原因，你必須依次對每個開采計劃求解（即下一個開采計劃會按一定格式加密，加密的方式與上一個開采計劃的答案有關）。具體的加密方式見輸入格式。
Input
第一行三個正整數 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。
Output
對于每個開采計劃，輸出一行兩個正整數，分别描述分子和分母。
Sample Input
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
Sample Output
1 1
1 2
1 1
9 10
3 4
HINT
輸入檔案給出的9個點和14條邊描述的平面圖如下所示：
第一個開采計劃，輸入的第1個值為3，是以該開采計劃對應的多邊形有(3+0) mod 8 +1=4個點，将接下的4個數3,0,4,7，分别代入(z_i+0) mod n + 1得到4個點的編号為4,1,5,8。計算出第一個開采計劃的分子為1，分母為1。
類似地，可計算出餘下開采計劃的多邊形的點數和點的編号：
第二個開采計劃對應的多邊形有3個點，編号分别為5, 6, 8。
第三個開采計劃對應的多邊形有6個點，編号分别為1, 2, 6, 5, 8, 4。
第四個開采計劃對應的多邊形有5個點，編号分别為1, 2, 6, 8, 4。
第五個開采計劃對應的多邊形有6個點，編号分别為1, 5, 6, 8, 7, 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樹。對于一個開采計劃，一定包括了對偶圖中的若幹條邊，并且這些邊圈出了對偶圖中的一個點集，這些點就是需要開采的點。我們記錄一下dfs樹的子樹點權和，那麼對于詢問的一條樹邊我們判斷它是進入子樹還是離開子樹，對應的答案加上或減去子樹的權值和。對于非樹邊直接忽略就好了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
char BUF[],*buf,*end;
#define getch() (buf==end?fread(BUF,1,2000000,stdin),buf=BUF,end=buf+2000000,*(buf++):*(buf++))
inline void Read(int &x){
static char c;
int f=;
for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-;
for(x=;c>='0'&&c<='9';c=getchar()) x=x*+c-'0';
x=x*f;
}
const int N=;
typedef long long ll;
struct point{
int x,y;
friend ll operator *(const point &a,const point &b){
return (ll)a.x*b.y-(ll)b.x*a.y;
}
friend point operator -(const point &a,const point &b){
point tmp;
tmp.x=a.x-b.x; tmp.y=a.y-b.y;
return tmp;
}
}p[N];
struct edge{
int u,v,id;
double ang;
edge(){}
edge(int a,int b,int k){
u=a; v=b; id=k;
ang=atan2((double)p[b].y-p[a].y,(double)p[b].x-p[a].x);
}
friend bool operator <(const edge &a,const edge &b){
return a.ang<b.ang;
}
}e[*N];
vector<edge> E[N],TE[N*];
int Nex[N*],v[N*],cnt=,num,rt;
int vi[N*],fa[N*],flag[N*];
int n,m,k,x,y,rec,q[N];
ll ans1,ans2,P,S[N*],S1[N*];
int Find(int x,const edge &a){
int mid,l=,r=E[x].size();
while(r-l>){
mid=(l+r)>>;
if(a<E[x][mid]) r=mid;
else l=mid;
}
return l;
}
ll gcd(ll a,ll b){
if(b==) return a;
return gcd(b,a%b);
}
void solve(){
int now,tmp,st; ll s;
for(int i=;i<=cnt;i++)
if(!v[i]){
s=; now=i; v[i]=++num; st=e[i].u;
while(){
tmp=Nex[now]; v[tmp]=num;
if(e[tmp].v==st) break;
s+=(p[e[tmp].u]-p[st])*(p[e[tmp].v]-p[st]);
now=tmp;
}
S[num]=s;
if(s<=) rt=num;
}
for(int i=;i<=cnt;i++)
TE[v[i]].push_back(edge(v[i],v[i^],i));
}
void dfs(int x){
vi[x]=; S1[x]=S[x]*S[x]; S[x]*=;
for(int i=;i<(int)TE[x].size();i++)
if(!vi[TE[x][i].v]){
fa[TE[x][i].v]=x;
flag[TE[x][i].id]=;
flag[TE[x][i].id^]=;
dfs(TE[x][i].v);
S[x]+=S[TE[x][i].v];
S1[x]+=S1[TE[x][i].v];
}
}
int main(){
Read(n); Read(m); Read(k);
for(int i=;i<=n;i++) Read(p[i].x),Read(p[i].y);
for(int i=;i<=m;i++) {
Read(x); Read(y);
++cnt; e[cnt]=edge(x,y,cnt);
E[x].push_back(e[cnt]);
++cnt; e[cnt]=edge(y,x,cnt);
E[y].push_back(e[cnt]);
}
for(int i=;i<=n;i++) sort(E[i].begin(),E[i].end());
for(int i=;i<=cnt;i++){
Nex[i]=Find(e[i].v,e[i^])-;
if(Nex[i]<) Nex[i]=E[e[i].v].size()-;
Nex[i]=E[e[i].v][Nex[i]].id;
}
solve(); dfs(rt);
for(int i=;i<=k;i++){
Read(q[]); q[]=(q[]+P)%n+;
for(int j=;j<=q[];j++) Read(q[j]),q[j]=(q[j]+P)%n+;
ans1=ans2=; q[++q[]]=q[];
for(int j=;j<q[];j++){
x=q[j]; y=q[j+];
int tmp=Find(x,edge(x,y,));
tmp=E[x][tmp].id;
if(!flag[tmp]) continue;
if(v[tmp]==fa[v[tmp^]]) ans1+=S[v[tmp^]],ans2+=S1[v[tmp^]];
else ans1-=S[v[tmp]],ans2-=S1[v[tmp]];
}
if(ans1<) ans1=-ans1,ans2=-ans2;
ll d=gcd(ans1,ans2); ans1/=d; ans2/=d;
printf("%lld %lld\n",P=ans2,ans1);
}
return ;
}