Description
如果一个点左右上下都有黑点，那么这个点也会变成黑点，问最后有多少个黑点\(n\leqslant 10^5\).
Solution
扫描线.
显然变化后的点并不会产生新点，因为他的产生就需要他上下左右有点。
可以把他们转化成一些横纵的互不相交的直线...然后求交点个数...就是扫描线...
Code
/**************************************************************Problem: 1818User: BeiYuLanguage: C++Result: AcceptedTime:1672 msMemory:16532 kb
****************************************************************/#include <bits/stdc++.h>
using namespace std;const int N = 300050;inline int in(int x=0,char s=getchar(),int v=1) { while(s>'9'||s<'0')v=s=='-'?-1:v,s=getchar();while(s>='0'&&s<='9')x=x*10+s-'0',s=getchar();return x*v; }int n,cp,cl,cy,ans;
int yy[N];
pair<int,int> pp[N];
struct P { int x,y,f; }p[N];
struct L { int x,y1,y2; }l[N];int cmpp(const P &a,const P &b) { return a.x==b.x?a.f>b.f:a.x<b.x; }
int cmpl(const L &a,const L &b) { return a.x<b.x; }void Add1(L a) { p[++cp]=(P) { a.y1,a.x,1 },p[++cp]=(P) { a.y2,a.x,-1 }; }
void Add2(L a) { l[++cl]=a; }
int Qy(int x) { return lower_bound(yy+1,yy+cy+1,x)-yy; }namespace Seg {int d[N<<2];#define lc (o<<1)#define rc (o<<1|1)#define mid ((l+r)>>1)void Update(int o) { d[o]=d[lc]+d[rc]; }void Add(int o,int l,int r,int x,int v) {
// cout<<o<<" "<<l<<" "<<r<<" "<<x<<" "<<v<<endl;if(l==r) { d[o]+=v;return; }if(x<=mid) Add(lc,l,mid,x,v);else Add(rc,mid+1,r,x,v);Update(o);}int Qur(int o,int l,int r,int L,int R) {
// cout<<o<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<endl;if(L<=l && r<=R) return d[o];int res=0;if(L<=mid) res+=Qur(lc,l,mid,L,R);if(R>mid) res+=Qur(rc,mid+1,r,L,R);return res;}
};int main() {n=in();for(int i=1;i<=n;i++) {int x=in(),y=in();pp[i]=make_pair(x,y);yy[++cy]=y,yy[++cy]=y-1,yy[++cy]=y+1;}sort(yy+1,yy+cy+1);cy=unique(yy+1,yy+cy+1)-yy-1;for(int i=1;i<=n;i++) pp[i].second=Qy(pp[i].second);sort(pp+1,pp+n+1);for(int i=1,j;i<=n;i=j+1) {for(j=i;j<=n && pp[i].first==pp[j+1].first;j++);for(int k=i;k<j;k++) Add2((L) { pp[k].first,pp[k].second+1,pp[k+1].second-1 });}for(int i=1;i<=n;i++) swap(pp[i].first,pp[i].second);sort(pp+1,pp+n+1);for(int i=1,j;i<=n;i=j+1) {for(j=i;j<=n && pp[i].first==pp[j+1].first;j++);for(int k=i;k<j;k++) if(pp[k].second+1<=pp[k+1].second-1)Add1((L) { pp[k].first,pp[k].second+1,pp[k+1].second-1 });}sort(p+1,p+cp+1,cmpp);sort(l+1,l+cl+1,cmpl);/* cout<<cp<<endl;for(int i=1;i<=cp;i++) cout<<p[i].x<<" "<<p[i].y<<" "<<p[i].f<<endl; cout<<cl<<endl;for(int i=1;i<=cl;i++) cout<<l[i].x<<" "<<l[i].y1<<" "<<l[i].y2<<endl;*/for(int i=1,j,k=1;i<=cl;i=j+1) {for(;k<=cp&&(p[k].x<l[i].x||(p[k].x==l[i].x&&p[k].f>0));k++) Seg::Add(1,1,cy,p[k].y,p[k].f);for(j=i;j+1<=cl && l[i].x==l[j+1].x;j++);for(int t=i;t<=j;t++) ans+=Seg::Qur(1,1,cy,l[t].y1,l[t].y2);for(;k<=cp && p[k].x==l[i].x;k++) Seg::Add(1,1,cy,p[k].y,p[k].f);}printf("%d\n",ans+n);return 0;
}
