Eva

Time Limit: 10 Sec  Memory Limit: 64 MB
Description

无限大正方形网格里有n个黑色的顶点，所有其他顶点都是白色的（网格的顶点即坐标为整数的点，又称整点）。每秒钟，所有内部白点同时变黑，直到不存在内部白点为止。你的任务是统计最后网格中的黑点个数。 内部白点的定义：一个白色的整点P(x,y)是内部白点当且仅当P在水平线的左边和右边各至少有一个黑点（即存在x1 < x < x2使得(x1,y)和(x2,y)都是黑点），且在竖直线的上边和下边各至少有一个黑点（即存在y1 < y < y2使得(x,y1)和(x,y2)都是黑点）。

输入第一行包含一个整数n，即初始黑点个数。以下n行每行包含两个整数(x,y)，即一个黑点的坐标。没有两个黑点的坐标相同，坐标的绝对值均不超过109。

输出仅一行，包含黑点的最终数目。如果变色过程永不终止，输出-1。

4
0 2
2 0
-2 0
0 -2

5

数据范围
36%的数据满足：n < = 500
64%的数据满足：n < = 30000
100%的数据满足：n < = 100000

/**************************************************************

    Problem: 1818

    User: ictsing

    Language: C++

    Result: Accepted

    Time:1460 ms

    Memory:22392 kb

****************************************************************/

 

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn = 100000+10;

const int maxm = maxn*10;

int hsh[maxn];

int c[maxn];

struct node{

   int x,y;

}nd[maxn];

struct segment{

   int x,y,l,r,k;

}seg[maxm];

int cnt=0,n;

bool cmp1(node a,node b)

{

    if(a.x==b.x) return a.y<b.y;

    return a.x<b.x;

}

bool cmp2(node a,node b)

{

    if(a.y==b.y) return a.x<b.x;

    return a.y<b.y;

}

bool cmp3(segment a,segment b)

{

    if(a.y==b.y) return a.k<b.k;

    return a.y<b.y;

}

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void init()

{

    n=read();

    for(int i=1;i<=n;i++)

        nd[i].x=read(),hsh[i]=nd[i].x,nd[i].y=read();

    sort(hsh+1,hsh+n+1);

}

int find(int x)

{

    int l=1,r=n;

    while(l<=r)

    {

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

        if(hsh[mid]==x) return mid;

        if(hsh[mid]<x) l=mid+1;

        else r=mid-1;

    }

}

void insrt(int k,int l,int r,int ovo)

{

    if(!k) seg[++cnt].l=find(l),seg[cnt].r=find(r),seg[cnt].y=ovo;

    else seg[++cnt].x=find(ovo),seg[cnt].y=l,seg[cnt].k=1,

         seg[++cnt].x=find(ovo),seg[cnt].y=r,seg[cnt].k=-1;

}

void build()

{

    sort(nd+1,nd+n+1,cmp1);

    for(int i=2;i<=n;i++)

        if(nd[i].x==nd[i-1].x) insrt(1,nd[i-1].y,nd[i].y,nd[i-1].x);

    sort(nd+1,nd+n+1,cmp2);

    for(int i=2;i<=n;i++)

        if(nd[i].y==nd[i-1].y) insrt(0,nd[i-1].x,nd[i].x,nd[i-1].y);

}

int lowbit(int x)

{

    return x&(-x);

}

void update(int x,int y)

{

    while(x<=n)

    {

        c[x]+=y;

        x+=lowbit(x);

    }

}

int query(int x)

{

    int s=0;

    while(x)

    {

        s+=c[x];

        x-=lowbit(x);

    }

    return s;

}

void work()

{

    sort(seg+1,seg+cnt+1,cmp3);

    int ans=0;

    for(int i=1;i<=cnt;i++)

        if(!seg[i].k) ans+=query(seg[i].r-1)-query(seg[i].l);

        else update(seg[i].x,seg[i].k);

    printf("%d\n",ans+n);

}

int main()

{

    init();

    build();

    work();

    return 0;

}

/*

4

0 2

2 0

-2 0

0 -2

 

5

 

*/