题意：给出一些点，如果存在一个$a$，使得（有点的横坐标大于$a$，有点的横坐标小于$a$，没有点的横坐标等于$a$）或（有点的纵坐标大于$a$，有点的纵坐标小于$a$，没有点的纵坐标等于$a$），则可以将它们分开，问最后可以把这些点分成多少份
题目提示得很明确了，就是要用分治的思想，直接找到分割的位置，递归处理
关键在于怎么着，如果扫一遍是会T的（如果运气不好，每次都在最后分割）
所以一头一尾向中间扫，最坏情况就是每次都在中间分割，这样是$O(nlog_2n)$的
扫的过程直接用两个set存点，一个以横坐标为第一关键字，另一个以纵坐标为第一关键字，就愉悦地解决了
#include<stdio.h>#include<set>#include<algorithm>using namespace std;struct point{int x,y;point(int a=0,int b=0){x=a;y=b;}};struct cmpx{bool operator()(point a,point b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;}};struct cmpy{bool operator()(point a,point b){if(a.y==b.y)return a.x<b.x;return a.y<b.y;}};bool ltx(point a,point b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;}typedef set<point,cmpx> stx;typedef set<point,cmpy> sty;int conq(stx&sx,sty&sy){if(sx.size()==1)return 1;stx sx1;sty sy1;stx::iterator itx1;stx::reverse_iterator itx2;sty::iterator ity1;sty::reverse_iterator ity2;itx1=sx.begin();itx2=sx.rbegin();ity1=sy.begin();ity2=sy.rbegin();int t;do{t=itx1->x;itx1++;if(itx1->x-t>1){while(sx.begin()->x<=t){sx1.insert(*sx.begin());sy1.insert(*sx.begin());sy.erase(*sx.begin());sx.erase(*sx.begin());}return conq(sx,sy)+conq(sx1,sy1);}t=itx2->x;itx2++;if(t-itx2->x>1){while(sx.rbegin()->x>=t){sx1.insert(*sx.rbegin());sy1.insert(*sx.rbegin());sy.erase(*sx.rbegin());sx.erase(*sx.rbegin());}return conq(sx,sy)+conq(sx1,sy1);}t=ity1->y;ity1++;if(ity1->y-t>1){while(sy.begin()->y<=t){sx1.insert(*sy.begin());sy1.insert(*sy.begin());sx.erase(*sy.begin());sy.erase(*sy.begin());}return conq(sx,sy)+conq(sx1,sy1);}t=ity2->y;ity2++;if(t-ity2->y>1){while(sy.rbegin()->y>=t){sx1.insert(*sy.rbegin());sy1.insert(*sy.rbegin());sx.erase(*sy.rbegin());sy.erase(*sy.rbegin());}return conq(sx,sy)+conq(sx1,sy1);}}while(ltx(*itx1,*itx2));return 1;}int main(){int n,i,x,y;stx sx;sty sy;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d",&x,&y);sx.insert(point(x,y));sy.insert(point(x,y));}printf("%d",conq(sx,sy));}[CF475F]Meta-universe
原文地址：http://www.cnblogs.com/jefflyy/p/7896270.html