Codeforces 97B Superset 平面分治

题目链接：点击打开链接

题意：

给定一个点集

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

添加完点后使得对于点集内任意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 
          
            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; }