题解

poj3179

一共有$n$个点，横纵坐标最大为$m$（$n$<=500,$m$<=10000)

二分

很容易想到二分正方形的边长r，然后去判断这个正方形能不能在平面包含c个点及以上。

枚举和贪心

检查边长能否成立时，我们可以根据图形想到一个贪心的思想：

若干个点，如果我们要构造一个面积最小的，能包含所有点的正方形，那么正方形的四条边上一定有点存在。

所以我们把每个点的横纵坐标投影到x轴和y轴上，我们就可以用投影的交点作为正方形的右上端点，枚举所有可能的正方形，来判断边长为r时，能否保证包含至少c个点。

前缀和+离散化的妙用

前缀和

根据上述，我们如果每个点每个点地去判断在不在正方形内，时间复杂度会很大。

因此我们用到前缀和来表示二维区间的点个数。

而我们把所有点的横纵坐标投影排序离散化，就得到了相对排序，可以直接作为前缀和的两个下标。

离散化的妙用

但同时有个问题出现：

​ 正方形 的右上端点已确定，我们根据不定的边长得到左下端点，可是左下端点的两个坐标不一定在点集中出现过，那么这时候我们怎么计算前缀和？

这时有个妙用：

​ [HTML_REMOVED] 我们知道了左下端点的坐标后，在两个轴上找到小于它的最大的，出现过的投影，我们计算它和右上端点的区间和，因为该点和真实的左下端点之间，并不存在任何其他点，因此在计算区间和时，二者等效。[HTML_REMOVED]

时间复杂度

预处理的时间复杂度：

$$ o( n^2*log(m)+m) $$

如果不预处理，直接在check函数中二分查找：
$$ o(n^2*log(n)^2) $$
根据$m$和$n$的取值来选取处理数据的方法。

实现的细节：

p ： 点集。 x y表示横纵坐标
xx yy ：原坐标 到 离散化后的排列的映射
x y ：离散化后的排列 到 原坐标的映射
s ：二维前缀和 下标对应的是离散化后的排列

如果 一个（x轴或y轴的）坐标在点集中没有出现
那么我们无法在离散化后的排列中找到对应的映射
为了方便计算一个坐标减去一个数值后的新坐标，在离散的数组中找到位置，再去计算前缀和
我们把坐标在离散化数组中对应的位置 ，用小于它的，在点集中出现过的第一个坐标的映射来代替。

比如
原坐标数组： 2 4 5 8 10
离散化后的排序：1 2 3 4 5

当坐标为6时，我们找到它之前最近的，在原坐标数组中出现的，那就是5
于是就有了<6,3>这样一个映射

我们这样处理数据，是为了计算区间和
例如坐标（9,8），我们以它为右下角建立r=3的正方形，左上的端点就是（6,5）
但是例如如果x=6在原坐标数组中没有出现，我们找到离它最近的，之前出现过的点，
用这个点计算和（9,8）之间的前缀和时，显然是等效的，
因为两者中间没有出现其他的点，否则不满足是最近的出现过的点的条件，因此其对应的二维区间总和相同。放在y轴也是一样的道理。

code：

//大致参考李煜东老师在GitHub上的代码
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <ctime>
#include <cstring>

using namespace std;

const int maxn=10010;

int c,n,tx,ty;
struct node {
    int x,y;
}p[505];
int cx[maxn],cy[maxn],s[505][505];
//xx表示x轴坐标 到 离散化后的点集x轴坐标的位置 的映射
//更确切：xx[i]表示 小于i的，最大的，出现在点集中的x轴坐标点 在离散化后的点集中的位置
int xx[maxn],yy[maxn];

//x表示 将点集的x轴坐标 按照大小排序后，第i个坐标所对应的 坐标大小为x[i]
int x[505],y[505];

bool check(int le) {
    for(int i=1;i<=tx;i++) {
        for(int j=1;j<=ty;j++) {
            int px=x[i]-le;
            int py=y[j]-le;
            if(px<0) px=0;
            if(py<0) py=0;
            px=xx[px];
            py=yy[py];
            int num=s[i][j]-s[i][py]-s[px][j]+s[px][py];
            if(num>=c) return true;
        }
    }
    return false;
}

int main() { 
    cin>>c>>n;

    for(int i=1;i<=n;i++) {
        cin>>p[i].x>>p[i].y;
        cx[p[i].x]++;
        cy[p[i].y]++;
    }
    //确保不会重复
    for(int i=1;i<=10000;i++) {
        if(cx[i]) x[++tx]=i;
        xx[i]=tx;
        if(cy[i]) y[++ty]=i;
        yy[i]=ty;
    }
    //预处理 s数组 
    for(int i=1;i<=n;i++) {
        int x_=xx[ p[i].x ];
        int y_=yy[ p[i].y ];
        s[x_][y_]++;
    }
    for(int i=1;i<=tx;i++) {
        for(int j=1;j<=ty;j++)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
    }


    int l=1,r=10000;
    while(l<r) {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}