Description

某人在山上种了 \(n\) 棵小树苗. 冬天来了, 温度急速下降, 小树苗脆弱得不堪一击, 于是 树主人想用一些塑料薄膜把这些小树遮盖起来, 经过一番长久的思考, 他决定用 \(3\) 个 \(L \times L\) 的正方形塑料薄膜将小树遮起来. 我们不妨将山建立一个平面直角坐标系, 设第 \(i\) 棵小树的坐标为 \((x_i, y_i)\),\(3\) 个 \(L \times L\) 的正方形的边要求平行于坐标轴, 一个点如果在正方形的边界上, 也算作被覆盖. 当然, 我们希望塑料薄膜面积越小 越好, 即求 \(L\) 最小值.

Input

第一行有一个正整数 \(n\), 表示有多少棵树. 接下来有 \(n\) 行, 第 \(i + 1\) 行有 \(2\) 个整数 \(x_i, y_i\), 表示第 \(i\) 棵树的坐标, 保证不会有 \(2\) 个树的坐标相同.

Output

一行, 输出最小的 \(L\) 值.

Sample Input

4
0 1
0 -1
1 0
-1 0

Sample Output

1

Data Range

对于 100% 的数据,\(n \leq 20000\)

Explanation

首先一开始就应该想到二分答案对不对啊~

但是重要的在于判断这些矩形应该放在哪里.

首先一定有某两个顶角必须被一个矩形覆盖住. 我们发现, 加在一起总共也就 \(16\) 种情况, 可以直接枚举前两个矩形放在哪里 (一定在角落里), 然后检查剩下的点一共有多少个, 分布在哪里, 是否能再用一个矩形盖住.

于是均摊下来总时间复杂度是 \(O(n \log n)\), 如果把点的坐标离散化的话.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 20100;
const int infinit = 0x0f3f3f3f;

int org_n, org_x[maxn], org_y[maxn];
int n, x[maxn], y[maxn]; // Unstable data.

void clean_area(int x1, int y1, int x2, int y2)
{
    int m = 0; rep(i, 1, n)
        if (x[i] < x1 || x[i] > x2 || y[i] < y1 || y[i] > y2)
            x[++m] = x[i],
            y[  m] = y[i];
    n = m;
    return ;
}

void get_corner(int& x1, int& y1, int& x2, int& y2)
{
    x1 = infinit, x2 = -infinit;
    y1 = infinit, y2 = -infinit;
    rep(i, 1, n) x1 = min(x[i], x1), x2 = max(x[i], x2),
        y1 = min(y[i], y1), y2 = max(y[i], y2);
    return ;
}

void eradicate_square(int id, int len)
{
    int x1, y1, x2, y2;
    get_corner(x1, y1, x2, y2);
    if (id == 1)      clean_area(x1, y1, x1 + len, y1 + len);
    else if (id == 2) clean_area(x2 - len, y1, x2, y1 + len);
    else if (id == 3) clean_area(x1, y2 - len, x1 + len, y2);
    else if (id == 4) clean_area(x2 - len, y2 - len, x2, y2);
    return ;
}

bool judge(int len)
{
    rep(nx, 1, 4) rep(ny, 1, 4) {
        n = org_n;
        rep(i, 1, org_n) x[i] = org_x[i],
            y[i] = org_y[i];
        // Attempting to get rid of another two.
        eradicate_square(nx, len);
        eradicate_square(ny, len);
        int x1, y1, x2, y2;
        get_corner(x1, y1, x2, y2);
        // If the rest constitutes a small-enough square, then it is nice.
        if (x2 - x1 <= len && y2 - y1 <= len)
            return true;
    }
    return false;
}

int main(int argc, char** argv)
{
    scanf("%d", &org_n);
    for (int i = 1; i <= org_n; i++)
        scanf("%d%d", &org_x[i], &org_y[i]);
    // Binary search the results.
    int l = 1, r = infinit;
    int res = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (judge(mid)) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("%d\n", res);
    return 0;
}