Inner Vertices Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 2422 Accepted: 666 Case Time Limit: 2000MS Description
There is an infinite square grid. Some vertices of the grid are black and other vertices are white.
A vertex V is called inner if it is both vertical-inner and horizontal-inner. A vertex V is called horizontal-inner if there are two such black vertices in the same row that V is located between them. A vertex V is called vertical-inner if there are two such black vertices in the same column that V is located between them.
On each step all white inner vertices became black while the other vertices PReserve their colors. The process stops when all the inner vertices are black.
Write a program that calculates a number of black vertices after the process stops.
Input
The first line of the input file contains one integer number n (0 ≤ n ≤ 100 000) — number of black vertices at the beginning.
The following n lines contain two integer numbers each — the coordinates of different black vertices. The coordinates do not exceed 109 by their absolute values.
Output
Output the number of black vertices when the process stops. If the process does not stop, output -1.
Sample Input
4 0 2 2 0 -2 0 0 -2 Sample Output
5 Hint 
題意：無限大棋盤，給定一些黑棋的位置，同時如果一個白棋上下左右都有黑棋這個白棋就會變成黑棋，求最終黑棋的個數，如果變化不會停止就返回-1. 思路：實際上這個變化一定會停止，簡單思考即可以知道。問題是會不會引起連鎖反應？其實不會，比如看下圖 
如果由1235點生成了4點，那么4567點又可以生成8點，但是其實有2點的時候就可以生成8點。所以如果生成的點可以生成新的點的前提其實在這個點生成之前就已經確定了。所以不存在只有新生成的某一個點才能生成另一個新點的說法。所以這個時候我們可以利用掃描線的思想。但是由于坐標巨大，所以我們必須對坐標進行離散化處理，然后掃描線中得線段樹的數組才開的出來。關于掃描線的知識請移步http://www.cnblogs.com/scau20110726/archive/2013/04/12/3016765.html，所以我們可以將每一個豎直方向的線段的下端點賦值1，上端點賦值-1，然后按照他們的y坐標排序，然后按照圖上所有黑棋的y坐標排序后在相同的y坐標中求兩個相鄰x坐標之間區域內有多少個線段的下端，那么對應的x坐標的這個y坐標就可以生成一個黑棋。 給出一組我自己的測試數據
112 01 14 13 20 33 35 32 410000 45 54 1000000000輸出16#include <cstdio>#include <vector>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn = 100010 * 2;typedef long long ll;typedef struct node//黑棋的位置{ int x,y;}node;node a[maxn];typedef struct line//豎直線段的前后端{ int y,x,value;}line;vector<line> que;//按照x從小到大，相同的x按照y值從小到大排序bool cmpx(node x,node y){ if(x.x<y.x) return true; else if(x.x>y.x) return false; else{ if(x.y<y.y) return true; else return false; }}bool tcmp(line x,line y){ return x.y < y.y;}//按照y值從小到大，相同的y按照x值從小到大排序bool cmpy(node x,node y){ if(x.y<y.y) return true; else if(x.y>y.y) return false; else{ if(x.x<y.x) return true; else return false; }}typedef struct addtree{ //區間用[ql,qr],[l,r]表示 int t[maxn*2];//現在由于坐標還沒有離散化，所以我們需要對坐標進行離散化，否則這個樹是建立不出來的 //向上更新區間和函數 //比如區間[1,8]我們要在5位置將原來的數加上2就需要傳入(5,2,1,1,8) void update(int loc,int x,int k,int l,int r){ if(l==r) t[k]+=x; else{ int mid = l + (r-l)/2; if(loc<=mid) update(loc,x,k*2,l,mid); else update(loc,x,k*2+1,mid+1,r); t[k] = t[k*2] + t[k*2+1]; } } //查詢區間和 //比如區間[1,8]我們要查詢[3,6]區間的區間和就要傳入(3,6,1,1,8) int query(int ql,int qr,int k,int l,int r){ if(ql<=l && r<=qr) return t[k]; int mid = l + (r-l)/2,ans=0; if(ql<=mid) ans+=query(ql,qr,k*2,l,mid); if(mid+1<=qr) ans+=query(ql,qr,k*2+1,mid+1,r); return ans; }}addtree;//單點加上一個值求區間和的線段樹addtree at;int main(){ int n; cin >> n; for(int i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y); //對x和y的坐標進行離散化 int maxx=1,maxy=1,nowloc=0,lastloc=0; sort(a,a+n,cmpx);//按照x從小到大到y從小到大排序 while(lastloc < n){ nowloc = lastloc; while(lastloc < n && a[lastloc].x==a[nowloc].x) lastloc++; for(int i=nowloc;i<lastloc;i++) a[i].x=maxx; maxx++; } nowloc=0;lastloc=0; sort(a,a+n,cmpy); while(lastloc < n){ nowloc = lastloc; while(lastloc < n && a[lastloc].y==a[nowloc].y) lastloc++; for(int i=nowloc;i<lastloc;i++) a[i].y=maxy; maxy++; } //離散化結束 sort(a,a+n,cmpx);//再次按照x坐標進行排序 //for(int i=0;i<n;i++) cout << a[i].x << " " << a[i].y << endl; for(int i=0;i<n-1;i++){ if(a[i].x==a[i+1].x){ que.push_back( (line){a[i].y,a[i].x,1} ); que.push_back( (line){a[i+1].y,a[i+1].x,-1} ); } } sort(que.begin(),que.end(),tcmp);//這里存儲的都是線段的兩個端點，但是還有非線段的點 sort(a,a+n,cmpy);//對所有的點進行按照y的排序 int cnt=0,res=n,len=que.size(); memset(at.t,0,sizeof(at.t)); for(int i=0;i<n-1;i++){ int nowy=a[i].y; //先處理線段的端點 while(cnt < len && que[cnt].y<=nowy){ at.update(que[cnt].x,que[cnt].value,1,1,maxn); cnt++; } //再處理一些區間的問題 if(a[i+1].y==a[i].y && a[i+1].x - a[i].x >1){ res += at.query(a[i].x+1,a[i+1].x-1,1,1,maxn); } } cout << res << endl; return 0;}
