【NOI2014模擬7.11】理想城市(city)

Description

Input

第1 行爲一個正整數N，爲理想城區塊的數目。
第2 行到第N+1 行，每行有兩個非負整數。第i+2 行爲第i 個區塊的座標vi = (xi， yi)。node

Output

輸出僅一行一個正整數，爲S 的值。因爲S 的值可能較大，你只需輸出S mod 10^9。web

Sample Input

11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6svg

Solution

這個作法很機智
由於圖的特殊性質，若是將同一行連續的方格縮成一個點，上下相連的連邊，必定可以構成一顆樹
題目要求的是距離，那麼先考慮兩兩點走過縱向的距離，橫向的至關於把圖翻轉90°再求一次
先把圖變成一棵樹，樹的每條邊連的兩個點就是原圖中上下相鄰的方格
那麼這條邊分開的兩個部分中的方格的距離必定會通過這條邊，也就是這條邊的貢獻是它兩邊的點的數量之積
完了，很簡單是否是？？spa

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 3123457
#define M 101000
#define ll long long
#define mo 1000000000ll
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
int last[M],next[M],to[M],tot=0,be[M];
ll ans=0,hs[N],bz[N],data[M],n,size[M];
int fx[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
struct node{
    int x,y;
}p[M];
int hash(ll x)
{
    int y=x%N;
    while(1)
    {
        if(hs[y]==0||hs[y]==x) break;
        y=(y+1)%N;
    }
    hs[y]=x;
    return y;
}
void putin(int x,int y)
{
    if(to[last[x]]==y) return;
    next[++tot]=last[x];last[x]=tot;to[tot]=y;
}
bool cnt(node x,node y){return (x.x<y.x)||((x.x==y.x)&&(x.y>y.y));}
void INPUT()
{
    scanf("%lld",&n);
    int mi1=mo,mi2=mo;
    fo(i,1,n) 
    {
        scanf("%d%d",&p[i].x,&p[i].y);
        mi1=min(mi1,p[i].x);mi2=min(mi2,p[i].y);
    }
    fo(i,1,n) p[i].x-=mi1-1,p[i].y-=mi2-1;
}
void RESET()
{
    sort(p+1,p+n+1,cnt);
    fo(i,1,n) bz[hash(p[i].x*n+p[i].y)]=i;
    fd(i,n,1)
    {
        ll x=p[i].x,y=p[i].y;
        if(be[i]==0)
        {
            be[i]=i;size[i]=1;
            fd(j,i-1,1)
                if(p[j].y==p[j+1].y+1) be[j]=i,size[i]++;else break;
        }
        int jy=hash((x+1)*n+y);
        if(bz[jy]) putin(be[i],be[bz[jy]]),putin(be[bz[jy]],be[i]);
    }
}
void dfs(int x,int fa)
{
    for(int i=last[x];i;i=next[i])
    {
        int y=to[i];
        if(y==fa) continue;
        dfs(y,x);
        size[x]+=size[y];
    }
    for(int i=last[x];i;i=next[i])
    {
        int y=to[i];
        if(y==fa) continue;
        ans=(ans+(size[y]*(n-size[y]))%mo)%mo;
    }
}
int main()
{
    freopen("city.in","r",stdin);
    freopen("city.out","w",stdout);
    INPUT();
    RESET();
    dfs(be[1],0);
    fo(i,1,n) swap(p[i].x,p[i].y);
    tot=0;
    fo(i,1,M-1) last[i]=size[i]=be[i]=0;
    fo(i,1,N-1) hs[i]=bz[i]=0;
    RESET();
    dfs(be[1],0);
    printf("%lld",ans);
}