题目链接：

题意：

给定一个点集

加入一些点后再把这个点集输出来。

加入完点后使得对于点集内随意2个点都满足以下2条中至少一条

1、在同一水平线上或在同一垂直线上

2、所围成的矩阵里有其它点。

思路：

平面分治

先把点按x轴排序，然后找到中间的点，做一条直线 x = a[mid].x;

然后把全部点都投影到这条直线上。那么对于左边的点就不须要再和右边的进行匹配了。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;typedef pair
           
             pii;const int inf = 1e9;template 
            
             inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?
            
           
          
         
        
       
      
     

0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } #define N 10005 pii a[N], b[N*20]; int top, n; void dfs(int l, int r){ int mid = (l+r)>>1, maxx = a[mid].first; for(int i = l; i <= r; i++) b[top++] = pii(maxx, a[i].second); if(l < mid) dfs(l, mid-1); if(mid < r) dfs(mid+1, r); } void input(){ for(int i = 1; i <= n; i++) rd(a[i].first), rd(a[i].second); sort(a+1, a+1+n); top = 0; } void output(){ sort(b, b+top); top = unique(b, b+top)-b; pt(top); putchar('\n'); for(int i = 0; i < top; i++) pt(b[i].first), putchar(' '), pt(b[i].second), putchar('\n'); } int main(){ while(rd(n)){ input(); dfs(1, n); output(); } return 0; }