Description

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

Input

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

Output

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

Sample Input

-

 -

Sample Output

数据范围

%的数据满足：n < =

%的数据满足：n < =

%的数据满足：n < = 

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(int i = a;i <= n;i++)

#define lv(i,a,n) for(int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

struct point

{

    int x,y;

}a[];

struct seg

{

    int k,x,y,r;

}s[];

int n;

int hsh[],cnt = ;

int tr[],ans = ;

bool cmp1(point a,point b)

{

    if(a.x == b.x)

    return a.y < b.y;

    else

    return a.x < b.x;

}

bool cmp2(point a,point b)

{

    if(a.y == b.y)

    return a.x < b.x;

    else

    return a.y < b.y;

}

bool cmp3(seg a,seg b)

{

    if(a.y == b.y)

    return a.k < b.k;

    else

    return a.y < b.y;

}

int find(int x)

{

    int l = ,r = n,mid;

    while(l <= r)

    {

        int mid = (l + r) >> ;

        if(hsh[mid] < x)

        l = mid + ;

        else if(hsh[mid] > x)

        r = mid - ;

        else return mid;

    }

}

void insert(int k,int l,int r,int t)

{

    if(!k)

    {

        s[++cnt].x = find(l);

        s[cnt].r = find(r);

        s[cnt].y = t;

    }

    else

    {

        s[++cnt].x = find(t);

        s[cnt].y = l;

        s[cnt].k = ;

        s[++cnt].x = find(t);

        s[cnt].y = r;

        s[cnt].k = -;

    }

}

int lowbit(int x)

{

    return x & -x;

}

void build()

{

    sort(a + ,a + n + ,cmp1);

    duke(i,,n)

    {

        if(a[i].x == a[i - ].x)

        insert(,a[i - ].y,a[i].y,a[i].x);

    }

    sort(a + ,a + n + ,cmp2);

    duke(i,,n)

    {

        if(a[i].y == a[i - ].y)

        insert(,a[i - ].x,a[i].x,a[i].y);

    }

}

void update(int x,int y)

{

    while(x <= n)

    {

        tr[x] += y;

        x += lowbit(x);

    }

}

int ask(int x)

{

    int s = ;

    while(x)

    {

        s += tr[x];

        x -= lowbit(x);

    }

    return s;

}

void work()

{

    duke(i,,cnt)

    {

        if(!s[i].k)

        ans += ask(s[i].r - ) - ask(s[i].x);

        else

        update(s[i].x,s[i].k);

    }

}

int main()

{

    read(n);

    duke(i,,n)

    {

        read(a[i].x);

        read(a[i].y);

        hsh[i] = a[i].x;

    }

    sort(hsh + ,hsh + n + );

    build();

    sort(s + ,s + cnt + ,cmp3);

    work();

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

    return ;

}

/*

4

0 2

2 0

-2 0

0 -2

*/