Python3 解法, 执行用时: 1446ms, 内存消耗: 8132K, 提交时间: 2022-05-03 16:18:58

import sys


def if_cover(pos, square):
    x, y = pos
    cx, cy, l = square

    if (x > cx + l / 2) or (x < cx - l / 2):
        return False
    elif (y > cy + l / 2) or (y < cy - l / 2):
        return False
    else:
        return True


def generate(pos_list):
    x_max, x_min, y_max, y_min = -float("inf"), float("inf"), -float("inf"), float("inf")
    if pos_list == []:
        return []
    for pos in pos_list:
        x, y = pos
        x_max, y_max = max(x_max, x), max(y_max, y)
        x_min, y_min = min(x_min, x), min(y_min, y)
    
    return [x_max, x_min, y_max, y_min]


def cover(area, l, direct):
    if area == []:
        return [None, None, None]

    x_max, x_min, y_max, y_min = area
    if direct == "UR":
        cx, cy = x_max - l / 2, y_max - l / 2
    elif direct == "UL":
        cx, cy = x_min + l / 2, y_max - l / 2
    elif direct == "DR":
        cx, cy = x_max - l / 2, y_min + l / 2
    elif direct == "DL":
        cx, cy = x_min + l / 2, y_min + l / 2
    else:
        assert False
    
    return [cx, cy, l]


def main():
    for idx, line in enumerate(sys.stdin):
        if idx == 0:
            n = line.split()
            n = int(n[0])
            tree_list = []
        else:
            x, y = line.split()
            x, y = int(x), int(y)
            tree_list.append([x, y])
            if idx == n:
                break

    area = generate(tree_list)
    l, r = 0, max(area[0] - area[1], area[2] - area[3])
    ans_list = []
    while l <= r:
        mid = (r - l) // 2 + l
        ans_flag = False

        for d1 in ["UL", "DL", "UR", "DR"]:
            if ans_flag:
                break
            s1 = cover(area, mid, d1)
            pos1_list = []
            for pos in tree_list:
                if not if_cover(pos, s1):
                    pos1_list.append(pos)
            
            area_1 = generate(pos1_list)
            for d2 in ["UL", "DL", "UR", "DR"]:
                if ans_flag:
                    break
                s2 = cover(area_1, mid, d2)
                pos2_list = []
                for pos in pos1_list:
                    if not if_cover(pos, s2):
                        pos2_list.append(pos)

                area_2 = generate(pos2_list)

                if (not area_2) or (max(area_2[0] - area_2[1], area_2[2] - area_2[3]) <= mid):
                    ans_flag = True

        if ans_flag:
            ans_list.append(mid)
            r = mid - 1 
        else:
            l = mid + 1

    print(min(ans_list))


if __name__ == "__main__":
    main()

C++(clang++ 11.0.1) 解法, 执行用时: 152ms, 内存消耗: 852K, 提交时间: 2022-09-27 14:58:31

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20010;
const int inf = 1<<30;
int n;
bool vis[maxn];
struct point{
    int x, y;
    point(){}
    point(int x, int y) : x(x), y(y) {}
    void read(){
        scanf("%d%d", &x, &y);
    }
}p[maxn];
bool check(int l, int step){
    if(step == 4){
        for(int i = 1; i <= n; i++){
            if(!vis[i]) return false;
        }
        return true;
    }
    int xl = inf, xr = -inf, yl = inf, yr = -inf;
    int X, Y;
    bool flag = 0;
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            xl = min(p[i].x, xl); xr = max(xr, p[i].x);
            yl = min(p[i].y, yl); yr = max(yr, p[i].y);
        }
    }
    for(int i = 1; i <= 4; i++){
        if(i == 1) X = xl, Y = yl;
        else if(i == 2) X = xr, Y = yl;
        else if(i == 3) X = xl, Y = yr;
        else X = xr, Y = yr;
        vector <int> xs;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && X - l <= p[j].x && p[j].x <= X + l && Y - l <= p[j].y && p[j].y <= Y + l){
                vis[j] = 1;
                xs.push_back(j);
            }
        }
        flag |= check(l, step + 1);
        for(int j = 0; j < xs.size(); j++){
            vis[xs[j]] = 0;
        }
    }
    return flag;
}
int main(){
    scanf("%d", &n);
    for(int i  = 1; i <= n; i++) p[i].read();
    int l = 0, r = inf;
    while(l < r){
        int mid = (l + r) / 2;
        if(check(mid, 1)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}