本文共 971 字，大约阅读时间需要 3 分钟。

题目大意：

      给定n个点的点集，要求向点集里添加一些点，使点集中的任意两个点满足下列三个条件中的一个：

      ①在同一行  ②在同一列

      ③以这两个点为对角构成的矩形的内部或者边缘包含其余的点

题解：

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

       然后把所有点都投影到这条直线上，这就保证了，任两个点之间至少能满足条件3（投影到轴上的点至少包含在矩形内），包含一种构造的思想。

        本题必须重载运算符，光在sort中写个cmp函树是不够的，因为set是自动排序的，而你给set一个结构体他不知道该怎样排序，所以需要在结构体内重载比较运算符。

       同时本题也是平面分治的一经典题

#include 
   
    #include 
    
     using namespace std;struct node{    int x,y;    bool operator <(const node &t)const    {        if(x==t.x)return y
     
      _set;void dfs(int l,int r){    if(l==r)return;    int mid=(l+r)>>1;    node tmp;    for(int i=l;i<=r;++i)    {        tmp.x=a[mid].x;        tmp.y=a[i].y;        _set.insert(tmp);    }    dfs(l,mid);    dfs(mid+1,r);}int main(){    //freopen("input.txt","r",stdin);    scanf("%d",&n);    for(int i=1;i<=n;++i)    {        scanf("%d%d",&a[i].x,&a[i].y);       _set.insert(a[i]);    }    sort(a+1,a+1+n);    dfs(1,n);    printf("%d\n",_set.size());    for(auto it:_set)        printf("%d %d\n",it.x,it.y);    return 0;}
     
    
   

转载地址：http://vkfgf.baihongyu.com/