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

  1. 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][ ...

  2. 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/ ...

  3. 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 ...

  4. [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 ...

  5. 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\ ...

  6. 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 ...

  7. 【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 ...

  8. 【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] ...

  9. 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

  1. 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 ...

  2. 【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 ...

  3. 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 ...

  4. 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) ...

  5. 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 ...

  6. 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 ...

  7. 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 ...

  8. 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 ...

  9. pycharm import scrapy Report errors ,No module named &#39;scrapy&#39;

    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 ...

  10. 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 . ...