Description

无限大正方形网格里有 \(n\) 个黑色的顶点, 所有其他顶点都是白色的 (网格的顶点即坐标为整数的点, 又称整点). 每秒钟, 所有内部白点同时变黑, 直到不存在内部白点为止. 你的任务是统计最后网格中的黑点个数.

内部白点的定义: 一个白色的整点 \(P(x,y)\) 是内部白点当且仅当 \(P\) 在水平线的左边和右边各至少有一个黑点 (即存在 \(x_1 \lt x \lt x_2\) 使得 \((x_1,y)\) 和 \((x_2,y)\) 都是黑点), 且在竖直线的上边和下边各至少有一个黑点 (即存在 \(y_1 \lt y \lt y_2\) 使得 \((x,y_1)\) 和 \((x,y_2)\) 都是黑点).

Input

输入第一行包含一个整数 \(n\), 即初始黑点个数.

以下 \(n\) 行每行包含两个整数 \((x,y)\), 即一个黑点的坐标. 没有两个黑点的坐标相同, 坐标的绝对值均不超过 \(10^9\).

Output

输出仅一行, 包含黑点的最终数目. 如果变色过程永不终止, 输出 \(-1\).

Sample Input

4
0 2
2 0
-2 0
0 -2

Sample Output

5

Data Range

36% 的数据满足:\(n \leq 500\) 64% 的数据满足:\(n \leq 30000\) 100% 的数据满足:\(n \leq 100000\)

Explanation

首先证明变色过程迟早药丸:

若变色过程总不停止, 则每个时刻总有新的点出生. 这些点出生之前一个时刻 (正) 上下左右都存在黑点, 那么它一定在整个点集 \(V\) 的 “曼哈顿凸包” 中----就是那个横平竖直的外接矩形. 这样一来这个凸包不会增大, 且点均为整点, 固然这个过程总是有限的.

然后证明一次就完成了变色过程:

假如某一个点因为缺少一个方向上的黑点从而不能成为黑点, 然而下一个时刻该方向上出现了黑点. 那么那一个黑点由于缺少对应方向上的黑点在这一个时刻并不能成为黑点, 矛盾.

所以所有即将成为黑点的点都将在第一时刻变为黑点.

问题转化为有多少点在四个方向上都有黑点.

考虑所有 \(x\) 轴相同的线段 (也就是点对), 以及 \(y\) 轴相同的线段.

然后从上到下扫描, 维护从左到右的对数.

上一个树状数组即可.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 200100;

struct point {
    int x, y;
};
bool cmp_x(point a, point b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
} bool cmp_y(point a, point b) {
    if (a.y == b.y) return a.x < b.x;
    return a.y < b.y;
} point pnt[maxn];

struct segmnt {
    int typ, x, y, r;
};
bool cmp_s(segmnt a, segmnt b) {
    if (a.y == b.y) return a.typ < b.typ;
    return a.y < b.y;
} segmnt seg[maxn*5];

class FenwickTree
{
public:
    int n, dat[maxn];
    void change(int x, int v)
    {
        for (; x <= n; x += x & (-x))
            dat[x] += v;
        return ;
    }
    int query(int x)
    {
        int sum = 0;
        for (; x > 0; x -= x & (-x))
            sum += dat[x];
        return sum;
    }
    void init(int n)
    {
        this->n = n;
        for (int i = 1; i <= n; i++)
            dat[i] = 0;
        return ;
    }
} fwt;

int n, scnt;
int hsh[maxn];

int find(int x)
{
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (hsh[mid] < x)
            l = mid + 1;
        else if (hsh[mid] > x)
            r = mid - 1;
        else
            return mid;
    }
    return 0;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &pnt[i].x, &pnt[i].y);
        hsh[i] = pnt[i].x;
    }
    // Sorting X-axis
    sort(hsh + 1, hsh + n + 1);
    // Creating segments for similar X-axis
    sort(pnt + 1, pnt + n + 1, cmp_x);
    for (int i = 2; i <= n; i++)
        if (pnt[i].x == pnt[i-1].x) {
            segmnt& s = seg[++scnt];
            s.x = find(pnt[i].x);
            s.y = pnt[i-1].y;
            s.typ = 1;
            segmnt& t = seg[++scnt];
            t.x = find(pnt[i].x);
            t.y = pnt[i].y;
            t.typ = -1;
        }
    // Creating segments for similar Y-axis
    sort(pnt + 1, pnt + n + 1, cmp_y);
    for (int i = 2; i <= n; i++)
        if (pnt[i].y == pnt[i-1].y) {
            segmnt& s = seg[++scnt];
            s.x = find(pnt[i-1].x);
            s.r = find(pnt[i].x);
            s.y = pnt[i].y;
            s.typ = 0;
        }
    // Sorting segments
    sort(seg + 1, seg + scnt + 1, cmp_s);
    // Constructing Fenwick tree
    int res = 0;
    fwt.init(n);
    for (int i = 1; i <= scnt; i++) {
        if (seg[i].typ == 0)
            res += fwt.query(seg[i].r - 1) - fwt.query(seg[i].x);
        else
            fwt.change(seg[i].x, seg[i].typ);
    }
    // Output
    printf("%d\n", res + n);
    return 0;
}