M_sea

洛谷3249 [HNOI2016]矿区
LuoguBZOJ分析首先将平面图转成对偶图。考虑怎么找到一个平面区域。首先把双向边转成两条单向边,这样每条边都属...
扫描右侧二维码阅读全文
26
2019/02

洛谷3249 [HNOI2016]矿区

Luogu

BZOJ

分析

首先将平面图转成对偶图。

考虑怎么找到一个平面区域。

首先把双向边转成两条单向边,这样每条边都属于一个区域。然后将以每个点为起点的边按极角排序。

对于每条边$(u,v)$,在以$t$为起点的边中找到$(v,u)$,排序后它的上一条边就是当前区域的下一条边。

这样一直到区域闭合,就找完了一个平面区域。

建好对偶图之后,找到任意一颗以无界域为根的生成树。(无界域指面积无限的部分)

然后标记所有在生成树上的边,并算出子树中的矿区面积和与平方和。

对于一个询问,先找到出现的边,如果不在生成树上就忽略。否则,如果它所在的面是子节点,就加上子树的面积,否则减去子树的面积。

至于为什么是对的,画个图就知道啦。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1200000+10;

struct Point { int x,y; } p[N];
typedef Point Vector;
Vector operator -(Point a,Point b) { return (Point){a.x-b.x,a.y-b.y}; }
inline ll cross(Vector a,Vector b) { return 1ll*a.x*b.y-1ll*a.y*b.x; }
struct Edge { int u,v,id; double deg; } e[N];
bool operator <(Edge a,Edge b) {
    return fabs(a.deg-b.deg)<1e-10?a.v<b.v:a.deg<b.deg;
}

int n,m,Q,root;
int cnt=1,tot=0;
int nxt[N],bel[N],fa[N],vis[N];
int intree[N],q[N];
ll s[N],ss[N];
vector<Edge> head[N],tr[N];

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){u,v,cnt,atan2(p[v].y-p[u].y,p[v].x-p[u].x)};
    head[u].push_back(e[cnt]);
}

inline void build() {
    for (re int i=1;i<=n;++i) sort(head[i].begin(),head[i].end());
    for (re int i=2;i<=cnt;++i) {
        int v=e[i].v;
        vector<Edge>::iterator it=lower_bound(head[v].begin(),head[v].end(),e[i^1]);
        if (it==head[v].begin()) it=head[v].end();
        --it; nxt[i]=it->id;
    }
    for (re int i=2;i<=cnt;++i) {
        if (bel[i]) continue;
        bel[i]=bel[nxt[i]]=++tot;
        for (re int j=nxt[i];e[j].v!=e[i].u;j=nxt[j],bel[j]=tot)
            s[tot]+=cross(p[e[j].u]-p[e[i].u],p[e[j].v]-p[e[i].u]);
        if (s[tot]<=0) root=tot;
    }
    for (re int i=2;i<=cnt;++i) tr[bel[i]].push_back((Edge){bel[i],bel[i^1],i});
}

inline void dfs(int u,int f) {
    fa[u]=f,ss[u]=1ll*s[u]*s[u],s[u]*=2,vis[u]=1;
    for (re int i=0,tmp=tr[u].size();i<tmp;++i) {
        int v=tr[u][i].v; if (vis[v]) continue;
        intree[tr[u][i].id]=intree[tr[u][i].id^1]=1;
        dfs(v,u); s[u]+=s[v],ss[u]+=ss[v];
    }
}

int main() {
    n=read(),m=read(),Q=read();
    for (re int i=1;i<=n;++i) p[i]=(Point){read(),read()};
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    build(); dfs(root,0);
    ll ans1=0,ans2=0;
    while (Q--) {
        int d=(read()+ans1)%n+1;
        for (re int i=1;i<=d;++i) q[i]=(read()+ans1)%n+1;
        q[d+1]=q[1],ans1=ans2=0;
        for (re int i=1;i<=d;++i) {
            int u=q[i],v=q[i+1];
            Edge tmp=(Edge){u,v,0,atan2(p[v].y-p[u].y,p[v].x-p[u].x)};
            vector<Edge>::iterator it=lower_bound(head[u].begin(),head[u].end(),tmp);
            int j=it->id;
            if (!intree[j]) continue;
            if (fa[bel[j]]==bel[j^1]) ans1+=ss[bel[j]],ans2+=s[bel[j]];
            else ans1-=ss[bel[j^1]],ans2-=s[bel[j^1]];
        }
        ll g=__gcd(ans1,ans2); ans1/=g,ans2/=g;
        printf("%lld %lld\n",ans1,ans2);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 01 PM

发表评论