https://www.cnblogs.com/ljh2000-jump/p/6423399.html

#include<cmath>

#include<vector>

#include<cstdio>

#include<algorithm>

#define rep(i,l,r) for (int i=(l); i<=(r); i++)

typedef long long ll;

using namespace std; const int N=;

int n,m,Q,x,y,d,cnt=,nxt[N],tot,rt,bel[N],fa[N],ask[N];

bool vis[N],in[N];

ll s[N],sp[N],fz,fm; struct P{ int x,y; }p[N];

P operator -(const P &a,const P &b){ return (P){a.x-b.x,a.y-b.y}; }

ll operator *(const P &a,const P &b){ return 1ll*a.x*b.y-1ll*b.x*a.y; } struct E{

int u,v,id; double sl;

E(){}; E(int a,int b,int i):u(a),v(b),id(i),sl(atan2(p[b].y-p[a].y,p[b].x-p[a].x)){}

}e[N];

bool operator <(const E &a,const E &b){ return a.sl<b.sl; }

vector<E>w[N],tr[N];

void add(int u,int v){ cnt++; e[cnt]=(E){u,v,cnt}; w[u].push_back(e[cnt]); } ll gcd(ll a,ll b){ return b ? gcd(b,a%b) : a; } int find(int x,E b){

int l=,r=w[x].size()-;

while (l<r){

int mid=(l+r+)>>;

if (b<w[x][mid]) r=mid-; else l=mid;

}

return l;

} void dfs(int x){

vis[x]=; sp[x]=s[x]*s[x]; s[x]<<=; int ed=tr[x].size()-;

rep(i,,ed){

int v=tr[x][i].v; if (vis[v]) continue;

fa[v]=x; in[tr[x][i].id]=in[tr[x][i].id^]=;

dfs(v); s[x]+=s[v]; sp[x]+=sp[v];

}

} int main(){

freopen("bzoj4541.in","r",stdin);

freopen("bzoj4541.out","w",stdout);

scanf("%d%d%d",&n,&m,&Q);

rep(i,,n) scanf("%d%d",&x,&y),p[i]=(P){x,y};

rep(i,,m) scanf("%d%d",&x,&y),add(x,y),add(y,x);

rep(i,,n) sort(w[i].begin(),w[i].end());

rep(i,,cnt){

int ne=find(e[i].v,e[i^])-;

if (ne==-) ne=w[e[i].v].size()-;

nxt[i]=w[e[i].v][ne].id;

}

rep(i,,cnt) if (!bel[i]){

bel[i]=bel[nxt[i]]=++tot;

for (int x=nxt[i]; e[x].v!=e[i].u; x=nxt[x],bel[x]=tot)

s[tot]+=(p[e[x].u]-p[e[i].u])*(p[e[x].v]-p[e[i].u]);

if (s[tot]<=) rt=tot;

}

rep(i,,cnt) tr[bel[i]].push_back(E(bel[i],bel[i^],i));

dfs(rt);

while (Q--){

scanf("%d",&d); d=(d+fz)%n+;

rep(i,,d) scanf("%d",&ask[i]),ask[i]=(ask[i]+fz)%n+;

ask[d+]=ask[]; fz=fm=;

rep(i,,d){

int x=w[ask[i]][find(ask[i],E(ask[i],ask[i+],))].id;

if (!in[x]) continue;

if (fa[bel[x]]==bel[x^]) fm+=s[bel[x]],fz+=sp[bel[x]];

else fm-=s[bel[x^]],fz-=sp[bel[x^]];

}

ll d=gcd(fz,fm); fz/=d; fm/=d; printf("%lld %lld\n",fz,fm);

}

return ;

}

## [BZOJ4541][HNOI2016] Mining area ( A planar graph is transformed into a dual graph ) More articles about

- BZOJ 4541: [Hnoi2016] Mining area A planar graph is transformed into a dual graph +DFS Trees
4541: [Hnoi2016] Mining area Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 433 Solved: 182[Submit][Status][ ...

- BZOJ4541 [Hnoi2016] Mining area
The copyright of this article belongs to ljh2000 And blog park , Welcome to reprint , But keep this statement , And give a link to the original , Thank You for Your Cooperation . The author of this article :ljh2000 The author blog :http://www.cnblogs.com/ljh2000-jump/ ...

- BZOJ4541 HNOI2016 Mining area （ A planar graph is transformed into a dual graph ）
Consider transforming a planar graph into a dual graph . In particular , Splitting an undirected edge into two directed edges . Every time you think about finding all the edges that surround a region . For the current consideration , Find the opposite edge of the edge in the out edge set of the end point of the edge , A successor in polar order , This trailing edge is also the edge that surrounds the region . this ...

- [HNOI2016] Mining area
[HNOI2016] Mining area A planar graph is transformed into a dual graph Method : 1. Divided into positive and negative one-way sides , Each side belongs to a face 2. Each point is in polar order sort Out of the way 3. Enumerate each edge , It's on this side nxt It's the one in front of the opposite side ( So what you find is the edge of the face, counter clockwise ...

- LOJ#2052. 「HNOI2016」 Mining area （ A planar graph is transformed into a dual graph ）
Topic Portal Answer key At last, I can turn a plane graph into a dual graph -- First, we split the undirected edge into two unidirectional edges , So each side belongs to a face . Then sort the edges starting from each point by polar angle , So for an edge \((u,v)\), We are at all with \(v\ ...

- bzoj 4541: [Hnoi2016] Mining area 【 A planar graph is transformed into a dual graph + Make trees 】
First, a planar graph is transformed into a dual graph , The idea is that each side has its own pros and cons , The edges of each point are sorted by polar angle , Then find each edge, the next in polar order in the out edge of its point of arrival , So it must be the edge of the smallest polygon that this edge belongs to , And then according to next Edge to find all the polygons , With triangulation ...

- 【LG3249】[HNOI2016] Mining area
[LG3249][HNOI2016] Mining area Topic Luogu Answer key Let's turn a planar graph into a dual graph , After building the dual graph, take out a spanning tree at will , Based on unbounded scope . It's easy to find the unbounded range , When we use the cross product to calculate the directed area , If it turns out to be negative, it means nothing ...

- 【BZOJ-2007】 At an altitude of Minimum cut （ A planar graph is transformed into a dual graph + shortest path ）
2007: [Noi2010] At an altitude of Time Limit: 20 Sec Memory Limit: 552 MBSubmit: 2095 Solved: 1002[Submit][Status] ...

- A planar graph is transformed into a dual graph (Bzoj1001： The wolf catches the rabbit )
If you only know how to do this problem with minimal cut, it's too spicy introduce From a senior plan : A graph whose edges do not intersect on a plane ( Edges can be drawn around ) Then the edges and edges of a planar graph form many regions ( It has to do with the way you draw ) Define dual graphs : Connect two adjacent areas to each other , shape ...

## Random recommendation

- Introduce , Introduce my underlying support library Net.Sz.CFramework
Net.Sz.CFramework It's my own bottom library , It's a proven underlying Library . contain : socket tcp agreement ,socket http Protocol thread pool , Threading model , Task model , Timer model , Log module, script module, some auxiliary ...

- 【JQGRID DOCUMENTATION】. Learning notes .2. Basic table
JqGrid An example of is JavaScript object , With attributes , Events and methods . Attributes can be strings , Numbers , Array , Boolean or any other object . 1 Calling convention : $("#grid_id").jqGr ...

- stay C# Record the exception log in the console and output
Recently made a small program , It is required to record the exception of program running in the console and output it to the specified folder , Here is my specific program code : public static void ErrorLog(Exception ex) { stri ...

- PhoneGap perhaps Cordova Under the framework Html5 in JS call Android Native code
PhoneGap perhaps Cordova Under the framework Html5 in JS call Android Native code Check the news > Look at the engine > Open source products 0 People collect this article , Published in 8 Hours before (2013-09-06 00:39) ...

- java The code calls the third party interface
One . utilize httpclient Here's the string parameter (url It's a third-party interface , With no arguments , Such as :http://192.168.16.200:8081/faceInfo/list,param yes url The following parameters ) pu ...

- iOS9.3 Describe how to install the file
iOS9.3 beta Description file installation tutorial :1. Copy the following address :http://bbs.feng.com/plugin.php?id=attachment_download:tongji&aid=11 ...

- luogu1397 [NOI2013] Matrix game ( Sum of equal ratio sequence )
A more obvious summation of equal ratio sequence , But one problem is n and m huge .. Considering that they appear on the power , So you can mold it P-1( Fermat's small Theorem ) however a or c be equal to 1 When , We can't use the sum formula of the equal ratio sequence , At this time we have to take n and m, It's going to be a mold again P ...

- complex sql Query statement
Views are also called virtual tables 1. Save the actual data in the table , The view holds the SELECT sentence , A view is also a table , The difference is whether to save the actual data . 2. Using views, you can query data across multiple tables . You can use SELECT Statements are made into views ...

- pycharm import scrapy Report errors ,No module named 'scrapy'
Local by downloading pip install scrapy After successful installation , stay pychram Inside import scrapy Report errors Later, I found a variety of solutions , reinstall wheel,twisted, Neither. , It turns out that it needs to be changed Pr ...

- java in garadle The project doesn't have src problem
https://www.jb51.net/article/142791.htm I had a problem the other day , Is the use of ider establish gradle After the project ,src The directory is not automatically generated , Today I would like to share with you how to solve . ...