题目分析

本题要求在二维平面上用 $K$ 个不相交的正方形覆盖所有 $N$ 个给定点，并最小化最大正方形的边长。这是一个典型的几何覆盖问题，但由于 $K \le 3$，我们可以针对不同的 $K$ 值设计专门的算法。

关键观察

$1$. 问题约束：

$K$ 个正方形必须互不相交（没有公共部分）

所有点必须在某个正方形内或边界上

目标：最小化最大正方形的边长（即最小化覆盖所有点所需的正方形最大尺寸）

$2$. $K=1$ 的情况：

当 $K=1$ 时，问题简化为求能覆盖所有点的最小正方形。这是一个经典问题：最小覆盖正方形可以通过计算点的最小外包矩形，然后扩展为正方形得到。

$3$. $K=2$ 的情况：

两个正方形必须不相交，因此它们之间必须有明确的水平或垂直分隔。我们可以考虑：

水平分隔：两个正方形在 x 方向分离

垂直分隔：两个正方形在 y 方向分离

$4$. $K=3$ 的情况：

三个正方形的布局更复杂，可能形成 L 形、T 形或其他排列。需要枚举所有可能的几何配置。

算法思路

总体框架

算法采用二分答案 + 几何检查的策略：

二分正方形的最大边长 $L$

对于给定的 $L$，检查是否存在 $K$ 个边长为 $L$ 的正方形能覆盖所有点

不断缩小 $L$ 的范围，找到最小的可行 $L$

几何变换技巧 为了简化问题处理，代码使用了多种几何变换：

翻转：关于 x 轴或 y 轴翻转

旋转：通过交换坐标实现 90° 旋转

对称：处理所有可能的对称情况

这样只需要处理几种标准情况，其他情况可以通过变换得到。

主要检查函数

1. check_two 函数 检查两个正方形是否能覆盖所有点。通过寻找一个右对齐的正方形和一个左对齐的正方形来实现。

2. low_high_check 函数 处理三个正方形的特定布局：两个正方形在两侧，一个正方形在中间。检查中间正方形的可能位置。

3. lowest_check 函数 另一种三个正方形的布局检查，基于最低点的分布。

4. equal_check 函数 检查三个正方形可以通过滑动窗口的方式放置。

5. v2_check 函数 处理两个正方形垂直分离的情况。

预处理与排序 代码对点进行了多种排序：

按 x 坐标排序

按 y 坐标排序

同时考虑翻转和旋转后的排序

这样可以在不同方向上进行高效搜索。

算法步骤

$1$. 输入与预处理：

读取 $N$ 和 $K$，以及所有点的坐标。为后续处理准备多个排序数组。

$2$. 处理 $K=1$ 的情况：

直接计算覆盖所有点的最小正方形并输出。

$3$. 二分搜索：

左边界 $lo = 0$

右边界 $hi = INF$（足够大的数）

在 $[lo, hi]$ 中二分查找最小的正方形边长 $L$

$4$. 检查函数 test：

对于给定的边长 $L$ 和 $K$ 值：

如果是 $K=1$，直接检查单个正方形

如果是 $K=2$，调用 check_two 等函数

如果是 $K=3$，调用各种三个正方形的检查函数

$5$. 输出结果：

找到最小的可行 $L$ 后，构造具体的正方形位置并输出。

时间复杂度

预处理排序：$O(N \log N)$

二分搜索：$O(\log (10^9)) \approx 30$ 次迭代

每次检查：$O(N)$ 或 $O(N \log N)$

总时间复杂度：$O(N \log N \log M)$，其中 $M$ 是坐标范围

对于 $N \le 10^5$，这是可行的。

空间复杂度

存储点：$O(N)$

多个排序数组：$O(N)$

辅助数组：$O(N)$

总空间复杂度为 $O(N)$。

正确性证明

$1$. 二分答案的正确性：

如果边长为 $L$ 可行，那么边长为 $L' > L$ 也一定可行（可以放大正方形）。因此满足单调性，可以使用二分搜索。

$2$. 覆盖检查的完备性：

对于 $K=2$ 和 $K=3$，代码考虑了所有可能的几何布局：

水平分离

垂直分离

L 形排列

T 形排列

通过几何变换（翻转、旋转），只需处理标准情况即可覆盖所有可能。

$3$. 不相交保证：

所有检查函数都确保正方形之间有明确的间隙（至少 1 单位的间隔），保证它们不相交。

代码实现详解

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)

struct pt {
    int x, y, ind;
    pt(int X, int Y, int I) {
        x = X, y = Y, ind = I;
    }
    pt() {}
};

struct rect {
    int assi;
    ll l, d, r, u;
    rect(ll L, ll D, ll R, ll U, int A = 2000000000) {
        l = L, d = D, r = R, u = U, assi = A;
    }
    rect() {
        l = d = r = u = 0, assi = -1;
    }
    void transform(bool a, bool b, bool c) {
        ll aux;

        if (a)
            aux = l, l = -r, r = -aux;

        if (b)
            aux = d, d = -u, u = -aux;

        if (c)
            swap(l, d), swap(r, u);
    }
};

struct sol {
    bool valid;
    rect re[3];
    sol() {
        valid = false;
    }
    sol(rect R1, rect R2, rect R3) {
        re[0] = R1, re[1] = R2, re[2] = R3, valid = true;
    }
    void print() {

        forn(i, 3) if (re[i].assi != -1)
            printf("%lld %lld %lld", re[i].l, re[i].d, re[i].u - re[i].d), printf("\n");
    }
    void dummySquare(int num) {
        int start = 2001000000;
        forn(i, 3) {
            num += (re[i].assi == -1);

            if (re[i].assi == -1 && num > 3)
                re[i] = rect(start, 0, start + 1, 1, 0), start += 2;
        }
    }
    void transform(bool a, bool b, bool c) {
        forn(i, 3) re[i].transform(a, b, c);
    }
};

const int MAXN = 100010, INF = 2000000100;
int n, k, ext[MAXN], calc[MAXN];
ll st[2 * MAXN], st1[MAXN], st2[MAXN];
bool seen[MAXN];
pt srt[2][2][2][MAXN], varg[MAXN];
rect le[2][2][2], oneans;

auto fstCmp = [](pt a, pt b) {
    return a.x < b.x;
};

auto sndCmp = [](pt a, pt b) {
    return a.y < b.y;
};

rect cover(pt *arr, int m) {
    if (m <= 0)
        return rect();

    int mn = INF, mx = -INF;
    forn(i, m) mn = min(mn, arr[i].y), mx = max(mx, arr[i].y);
    return rect(arr[0].x, mn, arr[m - 1].x, mx);
}

rect push_corner(rect re, int dir, int len) {
    switch (dir) {
    case 0:
        return rect(re.l, re.d, re.l + len, re.d + len);

    case 1:
        return rect(re.r - len, re.d, re.r, re.d + len);

    case 2:
        return rect(re.l, re.u - len, re.l + len, re.u);

    case 3:
        return rect(re.r - len, re.u - len, re.r, re.u);
    }
}

rect rightmost(pt *arr, int m, int side) {
    int mn = INF, mx = -INF;
    rect ret = rect();
    forn(i, m) {
        mx = max(mx, arr[i].y), mn = min(mn, arr[i].y);

        if (arr[i].x - arr[0].x > side || mx - mn > side)
            break;

        if (i == m - 1 || arr[i + 1].x != arr[i].x)
            ret = rect(arr[0].x, mn, arr[i].x, mx, i);
    }
    return ret;
}

sol low_high_check(pt *arr, int l, int r, int side) {

    int high_left = max_element(arr, arr + l, sndCmp)->y;
    int high_center = max_element(arr + l, arr + r, sndCmp)->y;
    int low_center = min_element(arr + l, arr + r, sndCmp)->y;
    int low_right = min_element(arr + r, arr + n, sndCmp)->y;

    if (high_left > high_center || low_center > low_right)
        return sol();

    ext[l] = low_center, ext[r - 1] = high_center;
    dforn(i, l) ext[i] = min(ext[i + 1], arr[i].y);
    forsn(i, r, n) ext[i] = max(ext[i - 1], arr[i].y);
    dforn(i, l) calc[i] = ext[i + 1] - arr[i].x;
    forsn(i, r, n) calc[i] = ext[i - 1] - arr[i].x;
    dforn(i, l - 1) calc[i] = max(calc[i + 1], calc[i]);
    forsn(i, r + 1, n) calc[i] = min(calc[i - 1], calc[i]);

    int pos = r;
    forn(i, l) {
        while (pos < n && (calc[pos] + 2 > calc[i] || (ext[pos - 1] == ext[i + 1] && arr[pos].x - arr[i].x == 2)))
            ++pos;

        int width = arr[pos].x - arr[i].x - 2, height = max(ext[pos - 1] - ext[i + 1], 1);

        if (height <= width && width < side) {
            ll left_edge = max(arr[i].x + 1, arr[r - 1].x - height);
            int szl = lower_bound(arr, arr + n, pt(left_edge, -INF, 0), fstCmp) - arr;
            int szr = upper_bound(arr, arr + n, pt(left_edge + height, INF, 0), fstCmp) - arr;

            return sol(push_corner(cover(arr, szl), 1, side),
                       push_corner(cover(arr + szr, n - szr), 0, side),
                       rect(left_edge, ext[i + 1], left_edge + height, ext[i + 1] + height));
        }
    }
    return sol();
}

sol lowest_check(pt *arr, pt *brr, int l, int r, int side) {

    if (arr[r - 1].x - arr[l].x > side)
        return sol();

    int pos = find_if(arr, arr + n, [&brr](pt a) {
        return a.ind == brr[0].ind;
    }) - arr;

    if (pos < l || pos >= r)
        return sol();

    int L = pos, R = pos;
    forn(i, n) seen[i] = false;
    forn(i, n) {
        seen[brr[i].ind] = true;

        while (L > 0 && seen[arr[L - 1].ind])
            --L;

        while (R < n - 1 && seen[arr[R + 1].ind])
            ++R;

        int height = max(brr[i].x - brr[0].x, 1);

        if (L <= l && R >= r - 1 && height <= side && (L == 0 || R == n - 1 ||
                (height <= arr[R + 1].x - arr[L - 1].x - 2))) {
            ll left_edge = max(L == 0 ? -INF : arr[L - 1].x + 1, arr[r - 1].x - height);
            int szl = lower_bound(arr, arr + n, pt(left_edge, -INF, 0), fstCmp) - arr;
            int szr = upper_bound(arr, arr + n, pt(left_edge + height, INF, 0), fstCmp) - arr;
            return sol(push_corner(cover(arr, szl), 1, side),
                       push_corner(cover(arr + szr, n - szr), 0, side),
                       rect(left_edge, brr[0].x, left_edge + height, brr[0].x + height));
        }
    }
    return sol();
}

sol equal_check(pt *arr, int l, int r, int side) {

    int L = 0, R = 0;
    deque<int> mn, mx;
    forn(i, n) st1[i] = arr[i].x + 1, st2[i] = arr[i].x - (ll)side;
    merge(st1, st1 + n, st2, st2 + n, st);
    mn.push_back(arr[0].y);
    mx.push_back(arr[0].y);
    forn(i, 2 * n) {
        while (R < n && arr[R + 1].x <= st[i] + side) {
            ++R;

            while (!mn.empty() && mn.back() > arr[R].y)
                mn.pop_back();

            while (!mx.empty() && mx.back() < arr[R].y)
                mx.pop_back();

            mx.push_back(arr[R].y);
            mn.push_back(arr[R].y);
        }

        while (L < n && arr[L].x < st[i]) {
            if (!mn.empty() && arr[L].y == mn.front())
                mn.pop_front();

            if (!mx.empty() && arr[L].y == mx.front())
                mx.pop_front();

            ++L;
        }

        if (L <= l && R >= r - 1 && mx.front() - mn.front() <= side) {
            ll left_edge = max(arr[L - 1].x + 1, arr[r - 1].x - side);
            return sol(push_corner(cover(arr, L), 1, side),
                       push_corner(cover(arr + R + 1, n - R - 1), 0, side),
                       rect(left_edge, mn.front(), left_edge + side, mn.front() + (ll)side));
        }
    }
    return sol();
}

sol check_two(pt *arr, int m, int side) {
    rect fst = rightmost(arr, m, side);
    rect snd = rightmost(arr + fst.assi + 1, m - fst.assi - 1, side);

    if ((fst.assi == -1 || snd.assi == -1) && fst.assi != m - 1 && snd.assi != m - 1)
        return sol();

    if (fst.assi + snd.assi + 2 == m)
        return sol(rect(), fst, snd);

    return sol();
}

sol v2_check(pt *arr, pt *brr, int side) {
    int m = 0;
    rect fst = rightmost(arr, n, side);
    forn(i, n) seen[i] = false;
    forn(i, fst.assi + 1) seen[arr[i].ind] = true;

    forn(i, n) if (!seen[brr[i].ind])
        varg[m++] = brr[i];

    sol ret = check_two(varg, m, side);

    if (m != 0 && !ret.valid)
        return sol();

    ret.transform(0, 0, 1);
    ret.re[0] = push_corner(fst, 1, side);
    ret.re[1] = push_corner(ret.re[1], 2, side);
    ret.re[2] = push_corner(ret.re[2], 0, side);

    return ret;
}

sol horizontal_checks(int side) {
    forn(i, 2) {
        sol ret = equal_check(srt[0][0][i], le[0][0][i].assi + 1, n - le[1][0][i].assi - 1, side);

        if (ret.valid) {
            ret.transform(0, 0, i);
            return ret;
        }
    }

    forn(i, 2) forn(j, 2) {
        sol ret = lowest_check(srt[0][i][j], srt[i][0][j ^ 1], le[0][i][j].assi + 1, n - le[1][i][j].assi - 1, side);

        if (ret.valid) {
            ret.transform(0, i, j);
            return ret;
        }

        ret = low_high_check(srt[0][i][j], le[0][i][j].assi + 1, n - le[1][i][j].assi - 1, side);

        if (ret.valid) {
            ret.transform(0, i, j);
            return ret;
        }
    }
    return sol();
}

sol cross_checks(int side) {
    forn(i, 2) forn(j, 2) {
        sol ret = v2_check(srt[i][0][j], srt[0][i][j ^ 1], side);

        if (ret.valid) {
            ret.transform(i, 0, j);
            return ret;
        }
    }
    return sol();
}

sol test(int type, int side) {
    if (side >= oneans.r - oneans.l)
        return sol(rect(), rect(), oneans);

    forn(i, 2) forn(j, 2) forn(w, 2) le[i][j][w] = rightmost(srt[i][j][w], n, side);

    forn(i, 2) if (le[0][0][i].assi + le[1][0][i].assi >= n - 2) {
        sol ret = check_two(srt[0][0][i], n, side);
        ret.re[1] = push_corner(ret.re[1], 1, side);
        ret.re[2] = push_corner(ret.re[2], 0, side);
        ret.transform(0, 0, i);
        return ret;
    }

    if (type == 2)
        return sol();

    sol ret = cross_checks(side);

    if (ret.valid)
        return ret;

    ret = horizontal_checks(side);

    if (ret.valid)
        return ret;

    return sol();
}


int main() {
    scanf("%d %d", &n, &k);
    forn(i, n) {
        int a, b;
        scanf("%d %d", &a, &b);
        srt[0][0][0][i] = pt(a, b, i);
        srt[0][0][1][i] = pt(b, a, i);
    }

    forn(i, 2) sort(srt[0][0][i], srt[0][0][i] + n, fstCmp);
    forn(i, 2) forn(j, n) srt[0][1][i][j] = pt(srt[0][0][i][j].x, -srt[0][0][i][j].y, srt[0][0][i][j].ind);
    forn(i, 2) forn(j, 2) forn(w, n) srt[1][i][j][w] = pt(-srt[0][i][j][n - 1 - w].x, srt[0][i][j][n - 1 - w].y,
            srt[0][i][j][n - 1 - w].ind);

    oneans = cover(srt[0][0][0], n);
    oneans = push_corner(oneans, 0, max(max(oneans.r - oneans.l, oneans.u - oneans.d), 1LL));

    if (k == 1) {
        sol(rect(), rect(), oneans).print();
        return 0;
    }

    int lo = 0, hi = INF;
    sol ans;

    while (hi - lo > 1) {
        int mid = ((hi - lo) >> 1) + lo;
        sol partial = test(k, mid);

        if (partial.valid)
            hi = mid, ans = partial;
        else
            lo = mid;
    }

    ans.dummySquare(k);
    ans.print();
}