建站实战干货

我声称我的做法是对的。

欢迎来 hack！

二分 \(L\)，我们判断能否用至多 \(K\) 个边长 \(\leq L\) 的正方形覆盖所有点。注意这里钦定每个正方形内都有点。

若仅使用一个正方形，判断是否有 \(\max(mxX-mnX,mxY-mnY)\leq L\) 即可。

对于两个不交的正方形，必然存在一个轴，使得这两个正方形在轴上对应的区间不交。如果钦定这个轴为主轴，那么对于所有主轴坐标相同的点，我们只关心次轴坐标的最小值和最大值。

若使用两个正方形，不妨钦定 \(x\) 轴为主轴。设所有不同的主轴坐标为 \(p_1<\cdots<p_m\)，那么我们可以枚举 \(1\leq i<m\)，判断能否用两个边长 \(\leq L\) 的正方形分别覆盖 \(x\leq p_i\) 和 \(x\geq p_{i+1}\) 的点即可。

若使用三个正方形，考察这三个正方形两两间的不交轴，至少有两个不交轴是相同的。不妨设这个相同的不交轴是 \(x\) 轴，那么这三个正方形两两间的不交轴只有 \((x,x,y)\) 和 \((x,x,x)\) 两种类型。

对于 \((x,x,y)\)，我们发现这三个正方形一定是这样的形式：

此时不难发现 \(A\) 一定是越大越好。因为若存在合法方案使得 \(A\) 的右边界能够向右延伸，我们延伸出去，再平移 \(B,C\) 的左边界即可得到另一个合法方案。设所有不同的主轴坐标为 \(p_1<\cdots<p_m\)，我们找出最大的 \(l\) 使得 \(A\) 能覆盖 \(x\leq p_l\) 的点，然后对 \(x>p_l\) 的点跑两个正方形的做法即可。

较为复杂的是 \((x,x,x)\)。此时三个正方形一定是这样的形式：

设 \(B\) 包含了所有 \(p_l\leq x\leq p_r\) 的点。考察 \(l,r\) 合法的条件：

• 显然 \(x\leq p_{l-1}\) 的点能被一个边长 \(\leq L\) 的正方形覆盖，\(x\geq p_{r+1}\) 的点也是。
• 而对于 \(p_l\leq x\leq p_r\) 的点，能包住它们的正方形的最小边长为 \(a=\max(p_r-p_l,d(l,r),1)\)，其中 \(d(l,r)=\max\limits_{p_l\leq x_i\leq p_r}y_i-\min\limits_{p_l\leq x_i\leq p_r}y_i\)。显然要满足 \(a\leq L\)。
• 考虑 \(B\) 能取到的最靠左的左边界为 \(\max(p_{l-1}+1,p_r-a)\)，于是还要满足 \(\max(p_{l-1}+1,p_r-a)+a\leq p_{r+1}-1\)。

对 \(r\) 从小到大扫描线。显然第一个条件是容易维护的，第二个条件双指针加上单调队列也很容易维护。

对于第三个条件，显然我们只用判断是否有 \(p_{l-1}+1+a\leq p_{r+1}-1\)。而观察到 \(p_{l-1}+1+p_r-p_l\leq p_r\leq p_{r+1}-1\)，因此实际上只需要判断是否有 \(p_{l-1}+1+\max(d(l,r),1)\leq p_{r+1}-1\)。使用线段树加单调栈容易维护出 \(p_{l-1}+d(l,r)\)，而前面两个条件会把 \(l\) 限制在一个区间内，所以可以直接查询区间最小值，为了构造方案还需要记录最小值位置。这样没有考虑到对 \(1\) 取 \(\max\)，注意到 \(d(l,r)=0\) 的 \(l\) 是一段后缀 \([s,r]\)，不难在扫 \(r\) 的同时维护这个 \(s\)。于是我们只需要分成两段区间来查询即可。

于是我们就得到了 \(\mathcal{O}(n\log{n})\) 的 check。

判定过程中记录方案类型和分界线即可得到构造。可以先通过分界线将点进行分组，然后对于同一组内的点，先求出包含该组内点的最小正方形，然后把这个正方形根据方案类型贴到四个角之一。这里要注意细节：对于 \((x,x,x)\) 类型的中间的正方形，直接贴到最左侧可能是错的，还需要考虑前面的正方形的右边界。\((y,y,y)\) 类型同理。

注意到我们二分时判定的是用至多 \(K\) 个边长 \(\leq L\) 的正方形能否覆盖所有点。所以构造方案时，若正方形个数不足 \(K\)，还需要在 \(3\times 10^9\) 的边界处补充若干个正方形。

实现起来有很多细节，可以结合代码感受。适度封装会写起来舒服很多。

代码

#include <bits/stdc++.h>using namespace std;using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair<int, int>;
const int MAXN = 1e5 + 5;
const ll inf = 1e18;template<typename T> T lowbit(T x) { return x & -x; }
template<typename T> void chkMin(T &x, T y) { x = y < x ? y : x; }
template<typename T> void chkMax(T &x, T y) { x = x < y ? y : x; }
constexpr int lg2(ll x) { return 63 ^ __builtin_clzll(x); }
constexpr ll bitCeil(ll x) { return x == 1 ? 1ll : 1ll << lg2(x - 1) + 1; }int n, k;
pair<ll, ll> pt[MAXN];
vector<int> ord[2];int top1, stk1[MAXN];
int top2, stk2[MAXN];
int hd1, tl1, Q1[MAXN];
int hd2, tl2, Q2[MAXN];struct Seg {ll x, l, r;
};vector<Seg> vec[2];int X(int p, int flag) {return !flag ? pt[p].first : pt[p].second;
}int Y(int p, int flag) {return !flag ? pt[p].second : pt[p].first;
}struct SegTree {
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)struct Node {ll mn;int pos;friend Node operator+(const Node &lhs, const Node &rhs) {return lhs.mn <= rhs.mn ? lhs : rhs;}Node &operator+=(const Node &rhs) {return *this = *this + rhs;}} nd[MAXN << 2];ll tg[MAXN << 2];void pushUp(int p) {nd[p] = nd[ls(p)] + nd[rs(p)];}void apply(int p, ll v) {tg[p] += v;nd[p].mn += v;}void pushDown(int p) {if (!tg[p]) return;apply(ls(p), tg[p]);apply(rs(p), tg[p]);tg[p] = 0;}void build(int p, int l, int r) {tg[p] = 0;nd[p] = {inf, l};if (l == r) return;int mid = l + r >> 1;build(ls(p), l, mid);build(rs(p), mid + 1, r);}void upd(int p, int l, int r, int x, ll v) {if (l == r) {nd[p].mn = v;return;}pushDown(p);int mid = l + r >> 1;if (x <= mid) upd(ls(p), l, mid, x, v);else upd(rs(p), mid + 1, r, x, v);pushUp(p);}void add(int p, int l, int r, int x, int y, ll v) {if (x <= l && y >= r) {apply(p, v);return;}pushDown(p);int mid = l + r >> 1;if (x <= mid) add(ls(p), l, mid, x, y, v);if (y > mid) add(rs(p), mid + 1, r, x, y, v);pushUp(p);}Node query(int p, int l, int r, int x, int y) {if (x > y) return {inf, -1};if (x <= l && y >= r) return nd[p];pushDown(p);int mid = l + r >> 1;Node res = {inf, -1};if (x <= mid) res = query(ls(p), l, mid, x, y);if (y > mid) res += query(rs(p), mid + 1, r, x, y);return res;}
#undef ls
#undef rs
} sgt;vector<Seg> comp(int flag, int tp = 0, int v = 0) {// tp = 1: X > v// tp = 2: X < v// tp = 3: Y > v// tp = 4: Y < vvector<Seg> res;for (int i : ord[flag]) {int x = X(i, flag), y = Y(i, flag);if (tp == 1 && y <= v) continue;if (tp == 2 && y >= v) continue;if (res.empty() || res.back().x != x) res.push_back({x, y, y});else res.back().r = y;}return res;
}int getPre(const vector<Seg> &vec, int L) {if (vec.empty()) return -1;int res = -1;ll mnY = inf, mxY = -inf;for (int i = 0; i < vec.size(); ++i) {auto [x, l, r] = vec[i];chkMin(mnY, l);chkMax(mxY, r);if (x - vec[0].x <= L && mxY - mnY <= L) res = i;else break;}return res;
}int getSuf(const vector<Seg> &vec, int L) {if (vec.empty()) return 0;int res = vec.size();ll mnY = inf, mxY = -inf;for (int i = vec.size() - 1; i >= 0; --i) {auto [x, l, r] = vec[i];chkMin(mnY, l);chkMax(mxY, r);if (vec.back().x - x <= L && mxY - mnY <= L) res = i;else break;}return res;
}bool one(ll L) {ll mnX = inf, mxX = -inf, mnY = inf, mxY = -inf;for (int i = 0; i < n; ++i) {auto [x, y] = pt[i];chkMin(mnX, x);chkMax(mxX, x);chkMin(mnY, y);chkMax(mxY, y);}return max(mxX - mnX, mxY - mnY) <= L;
}pair<bool, ll> two(const vector<Seg> &vec, int L) {if (vec.size() < 2) return {false, 0};int l = max(getSuf(vec, L) - 1, 0), r = min(getPre(vec, L), (int)vec.size() - 2);return {l <= r, vec[l].x};
}tuple<bool, ll, ll> three(const vector<Seg> &vec, int L) {int sz = vec.size();if (sz < 3) return {false, 0, 0};int pre = getPre(vec, L);if (pre == -1) return {false, 0, 0};vector<int> suf(sz);ll mnY = inf, mxY = -inf;for (int i = sz - 1; i >= 0; --i) {auto [x, l, r] = vec[i];chkMin(mnY, l);chkMax(mxY, r);suf[i] = vec.back().x - x <= L && mxY - mnY <= L;}sgt.build(1, 0, sz - 1);stk1[top1 = 0] = stk2[top2 = 0] = -1;hd1 = hd2 = 1;tl1 = tl2 = 0;int pt1 = 0, pt2 = 1;for (int r = 0; r < sz; ++r) {while (top1 && vec[stk1[top1]].r <= vec[r].r) {sgt.add(1, 0, sz - 1, stk1[top1 - 1] + 1, stk1[top1], vec[r].r - vec[stk1[top1]].r);--top1;}stk1[++top1] = r;while (top2 && vec[stk2[top2]].l >= vec[r].l) {sgt.add(1, 0, sz - 1, stk2[top2 - 1] + 1, stk2[top2], vec[stk2[top2]].l - vec[r].l);--top2;}stk2[++top2] = r;sgt.upd(1, 0, sz - 1, r, (r ? vec[r - 1].x : 0) + vec[r].r - vec[r].l);while (hd1 <= tl1 && vec[Q1[tl1]].r <= vec[r].r) --tl1;Q1[++tl1] = r;while (hd2 <= tl2 && vec[Q2[tl2]].l >= vec[r].l) --tl2;Q2[++tl2] = r;while (pt1 <= r && (vec[r].x - vec[pt1].x > L || vec[Q1[hd1]].r - vec[Q2[hd2]].l > L)) {if (Q1[hd1] == pt1) ++hd1;if (Q2[hd2] == pt1) ++hd2;++pt1;}if (vec[r].l != vec[r].r) pt2 = r + 1;else if (!r || vec[r - 1].l != vec[r - 1].r || vec[r - 1].l != vec[r].l) pt2 = r;if (!r || r == sz - 1 || !suf[r + 1]) continue;int l1 = max(pt1, 1), r1 = min(pre + 1, r);if (l1 > r1) continue;auto res1 = sgt.query(1, 0, sz - 1, l1, min(pt2 - 1, r1));auto res2 = sgt.query(1, 0, sz - 1, max(l1, pt2), r1);++res2.mn;auto res = res1 + res2;if (res.mn + 1 < vec[r + 1].x) return {true, vec[res.pos - 1].x, vec[r].x};}return {false, 0, 0};
}pair<bool, tuple<int, ll, ll>> check(int L) {if (one(L)) return {true, {0, 0, 0}};if (k >= 2){auto [ok1, x1] = two(vec[0], L);if (ok1) return {true, {1, x1, 0}};auto [ok2, x2] = two(vec[1], L);if (ok2) return {true, {2, x2, 0}};}if (k == 3) {int p = getPre(vec[0], L);if (p != -1) {auto [ok3, x3] = two(comp(1, 1, vec[0][p].x), L);if (ok3) return {true, {3, vec[0][p].x, x3}};}p = getSuf(vec[0], L);if (p != vec[0].size()) {auto [ok4, x4] = two(comp(1, 2, vec[0][p].x), L);if (ok4) return {true, {4, vec[0][p].x, x4}};}p = getPre(vec[1], L);if (p != -1) {auto [ok5, x5] = two(comp(0, 1, vec[1][p].x), L);if (ok5) return {true, {5, vec[1][p].x, x5}};}p = getSuf(vec[1], L);if (p != vec[1].size()) {auto [ok6, x6] = two(comp(0, 2, vec[1][p].x), L);if (ok6) return {true, {6, vec[1][p].x, x6}};}auto [ok7, a7, b7] = three(vec[0], L);if (ok7) return {true, {7, a7, b7}};auto [ok8, a8, b8] = three(vec[1], L);if (ok8) return {true, {8, a8, b8}};}return {false, {0, 0, 0}};
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> k;for (int i = 0; i < n; ++i) {int x, y;cin >> x >> y;pt[i] = {x, y};}for (int flag : {0, 1}) {ord[flag].resize(n);iota(ord[flag].begin(), ord[flag].end(), 0);sort(ord[flag].begin(), ord[flag].end(), [&](int lhs, int rhs) {return X(lhs, flag) != X(rhs, flag) ? X(lhs, flag) < X(rhs, flag) : Y(lhs, flag) < Y(rhs, flag);});vec[flag] = comp(flag);}ll l = 1, r = 2e9;tuple<int, ll, ll> ans;auto [ok1, res1] = check(r);if (ok1) ans = res1;while (l < r) {ll mid = l + r >> 1;auto [ok, res] = check(mid);if (ok) {r = mid;ans = res;} else {l = mid + 1;}}auto [tp, a, b] = ans;int nk = !tp ? 1 : (tp <= 2 ? 2 : 3);vector<ll> mnX(nk, inf), mxX(nk, -inf), mnY(nk, inf), mxY(nk, -inf);for (int i = 0; i < n; ++i) {auto [x, y] = pt[i];int c;if (!tp) c = 0;else if (tp == 1) c = x > a;else if (tp == 2) c = y > a;else if (tp == 3) c = x <= a ? 0 : (y <= b ? 1 : 2);else if (tp == 4) c = x >= a ? 0 : (y <= b ? 1 : 2);else if (tp == 5) c = y <= a ? 0 : (x <= b ? 1 : 2);else if (tp == 6) c = y >= a ? 0 : (x <= b ? 1 : 2);else if (tp == 7) c = x <= a ? 0 : (x <= b ? 1 : 2);else c = y <= a ? 0 : (y <= b ? 1 : 2);chkMin(mnX[c], x);chkMax(mxX[c], x);chkMin(mnY[c], y);chkMax(mxY[c], y);}// 0: (mnX, mnY)// 1: (mxX, mnY)// 2: (mnX, mxY)// 3: (mxX, mxY)vector<int> ctp;if (!tp) ctp = {0};else if (tp == 1) ctp = {1, 0};else if (tp == 2) ctp = {2, 0};else if (tp == 3) ctp = {1, 2, 0};else if (tp == 4) ctp = {0, 3, 1};else if (tp == 5) ctp = {2, 1, 0};else if (tp == 6) ctp = {0, 3, 2};else if (tp == 7) ctp = {1, 1, 0};else ctp = {2, 2, 0};for (int i = 0; i < nk; ++i) {ll L = max({mxX[i] - mnX[i], mxY[i] - mnY[i], 1ll});if (!ctp[i]) {cout << mnX[i] << ' ' << mnY[i] << ' ' << L << '\n';} else if (ctp[i] == 1) {ll x = mxX[i] - L;if (tp == 7 && i == 1) chkMax(x, mxX[0] + 1);cout << x << ' ' << mnY[i] << ' ' << L << '\n';} else if (ctp[i] == 2) {ll y = mxY[i] - L;if (tp == 8 && i == 1) chkMax(y, mxY[0] + 1);cout << mnX[i] << ' ' << y << ' ' << L << '\n';} else {cout << mxX[i] - L << ' ' << mxY[i] - L << ' ' << L << '\n';}}ll f = 3e9;if (nk < k) cout << f << ' ' << f << ' ' << 1 << '\n';if (nk + 1 < k) cout << f << ' ' << -f << ' ' << 1 << '\n';return 0;
}