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
输出仅一行，包含黑点的最终数目。如果变色过程永不终止，输出-1。
Sample Input
4
0 2
2 0
-2 0
0 -2
0 2
2 0
-2 0
0 -2
Sample Output
5
数据范围
36%的数据满足：n < = 500
64%的数据满足：n < = 30000
100%的数据满足：n < = 100000
数据范围
36%的数据满足：n < = 500
64%的数据满足：n < = 30000
100%的数据满足：n < = 100000
正解：扫描线+树状数组。
容易发现，如果一个白点的上下左右都有黑点，那么它就能变成白点。
所以点是可以直接离散化的，无数点的情况也是没有的。
于是直接写一个扫描线，扫描每一列，然后用树状数组统计每一行是否上下都有黑点就行了。
#include <bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define lb(x) (x & -x)
#define inf (1<<30)
#define N (100005) using namespace std; struct point{ int x,y; }p[N]; vector<int> g[N];
int hsh[N],num[N],cnt[N],can[N],c[N],mn[N],mx[N],n,tot;
ll ans; il int gi(){
RG int x=,q=; RG char ch=getchar();
while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar();
while (ch>='' && ch<='') x=x*+ch-,ch=getchar();
return q*x;
} il void add(RG int x,RG int v){
for (;x<=n;x+=lb(x)) c[x]+=v; return;
} il int query(RG int x){
RG int res=;
for (;x;x^=lb(x)) res+=c[x]; return res;
} int main(){
#ifndef ONLINE_JUDGE
freopen("white.in","r",stdin);
freopen("white.out","w",stdout);
#endif
n=gi();
for (RG int i=;i<=n;++i) hsh[++tot]=p[i].x=gi(),p[i].y=gi();
sort(hsh+,hsh+tot+),tot=unique(hsh+,hsh+tot+)-hsh-;
for (RG int i=;i<=n;++i) p[i].x=lower_bound(hsh+,hsh+tot+,p[i].x)-hsh;
for (RG int i=;i<=n;++i) mn[i]=inf,mx[i]=;
tot=; for (RG int i=;i<=n;++i) hsh[++tot]=p[i].y;
sort(hsh+,hsh+tot+),tot=unique(hsh+,hsh+tot+)-hsh-;
for (RG int i=;i<=n;++i) p[i].y=lower_bound(hsh+,hsh+tot+,p[i].y)-hsh;
for (RG int i=;i<=n;++i){
g[p[i].x].push_back(i),++cnt[p[i].y];
mn[p[i].x]=min(mn[p[i].x],p[i].y),mx[p[i].x]=max(mx[p[i].x],p[i].y);
}
for (RG int i=;i<=n;++i){
if (mn[i]>mx[i]) continue;
for (RG int j=,k;j<g[i].size();++j){
k=p[g[i][j]].y,++num[k];
if (can[k]!=(num[k]&&cnt[k])) add(k,),can[k]=;
}
if (mn[i]!=mx[i]) ans+=query(mx[i]-)-query(mn[i])+; else ++ans;
for (RG int j=,k;j<g[i].size();++j){
k=p[g[i][j]].y,--cnt[k];
if (can[k]!=(num[k]&&cnt[k])) add(k,-),can[k]=;
}
}
cout<<ans; return ;
}