#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 inf = 1ll << 40;
constexpr i64 limit = 1000000000ll;
struct Answer {
i64 width;
std::array<std::tuple<i64, i64, i64, i64, i64>, 3> points;
};
bool operator <(const Answer &a, const Answer &b) {
return a.width < b.width;
}
using T = std::pair<i64, int>;
using F = i64;
T operate(T a, T b) {
return std::max(a, b);
}
T identity_T() {
return std::make_pair(-inf, 0);
}
F composite(F a, F b) {
return a + b;
}
T map(F a, T b) {
return {b.first + a, b.second};
}
F identity_F() {
return 0;
}
class lazy_segtree {
int n, size, logn;
std::vector<T> data;
std::vector<F> lazy;
void update(int i) {
data[i] = operate(data[2 * i], data[2 * i + 1]);
}
void apply(int i, const F &v) {
data[i] = map(v, data[i]);
if (i < size) {
lazy[i] = composite(lazy[i], v);
}
}
void flush(int i) {
apply(2 * i, lazy[i]);
apply(2 * i + 1, lazy[i]);
lazy[i] = identity_F();
}
void push1(int i) {
for (int d = logn; d >= 1; --d) {
if ((i >> d) << d != i) flush(i >> d);
}
}
void push2(int i) {
for (int d = logn; d >= 1; --d) {
if ((i >> d) << d != i) flush((i - 1) >> d);
}
}
void pull1(int i) {
for (int d = 1; d <= logn; ++d) {
if (((i >> d) << d) != i) update(i >> d);
}
}
void pull2(int i) {
for (int d = 1; d <= logn; ++d) {
if (((i >> d) << d) != i) update((i - 1) >> d);
}
}
public:
lazy_segtree(std::vector<T> vec) : n(vec.size()) {
size = 1;
logn = 0;
while (size < n) {
++logn;
size *= 2;
}
data.assign(2 * size, identity_T());
lazy.assign(size, identity_F());
for (int i = 0; i < n; ++i) {
data[i + size] = vec[i];
}
for (int i = size - 1; i >= 1; --i) {
update(i);
}
}
void operate_range(int l, int r, F x) {
l += size;
r += size;
push1(l);
push2(r);
for (int l2 = l, r2 = r; l2 < r2; l2 /= 2, r2 /= 2) {
if (l2 & 1) {
apply(l2++, x);
}
if (r2 & 1) {
apply(--r2, x);
}
}
pull1(l);
pull2(r);
}
void operate_point(int i, F x) {
operate_range(i, i + 1, x);
}
T fold(int l, int r) {
l += size;
r += size;
push1(l);
push2(r);
T ml = identity_T(), mr = identity_T();
while (l < r) {
if (l & 1) {
ml = operate(ml, data[l++]);
}
if (r & 1) {
mr = operate(data[--r], mr);
}
l /= 2;
r /= 2;
}
return operate(ml, mr);
}
};
int main() {
int N, K;
std::cin >> N >> K;
std::vector<i64> X(N), Y(N);
for (int i = 0; i < N; ++i) {
std::cin >> X[i] >> Y[i];
}
auto rotate = [&](const i64 x, const i64 y) {
return std::make_pair(y, -x);
};
auto reverse_rotate = [&](const i64 x, const i64 y) {
return std::make_pair(-y, x);
};
auto solve_k1 = [&]() -> Answer {
const i64 max_x = *std::max_element(X.begin(), X.end());
const i64 min_x = *std::min_element(X.begin(), X.end());
const i64 max_y = *std::max_element(Y.begin(), Y.end());
const i64 min_y = *std::min_element(Y.begin(), Y.end());
Answer ans;
ans.width = std::max(max_x - min_x, max_y - min_y);
ans.points[0] = std::make_tuple(min_x, min_y, max_x, max_y, ans.width);
ans.points[1] = std::make_tuple(-3 * limit, -3 * limit, -3 * limit + 1, -3 * limit + 1, 1);
ans.points[2] = std::make_tuple(3 * limit - 1, 3 * limit - 1, 3 * limit, 3 * limit, 1);
return ans;
};
auto solve_k2sub = [](int N, std::vector<std::pair<i64, i64>> C) {
std::vector<i64> max_y_l(N + 1), min_y_l(N + 1), max_y_r(N + 1), min_y_r(N + 1);
max_y_l[0] = max_y_r[N] = -inf;
min_y_l[0] = min_y_r[N] = inf;
for (int i = 0; i < N; ++i) {
max_y_l[i + 1] = min_y_l[i + 1] = C[i].second;
max_y_r[i] = min_y_r[i] = C[i].second;
}
for (int i = 0; i < N; ++i) {
max_y_l[i + 1] = std::max(max_y_l[i + 1], max_y_l[i]);
min_y_l[i + 1] = std::min(min_y_l[i + 1], min_y_l[i]);
}
for (int i = N; i > 0; --i) {
max_y_r[i - 1] = std::max(max_y_r[i - 1], max_y_r[i]);
min_y_r[i - 1] = std::min(min_y_r[i - 1], min_y_r[i]);
}
Answer ret;
ret.width = inf;
for (int i = 1; i < N; ++i) {
const i64 max_x1 = C[i - 1].first, min_x1 = C[0].first;
const i64 max_x2 = C[N - 1].first, min_x2 = C[i].first;
const i64 max_y1 = max_y_l[i], min_y1 = min_y_l[i];
const i64 max_y2 = max_y_r[i], min_y2 = min_y_r[i];
if (C[i - 1].first == C[i].first) {
if (std::max(min_y1, min_y2) <= std::min(max_y1, max_y2)) {
continue;
}
}
Answer cp;
const i64 w1 = std::max({max_x1 - min_x1, max_y1 - min_y1, 1ll});
const i64 w2 = std::max({max_x2 - min_x2, max_y2 - min_y2, 1ll});
cp.points[0] = std::make_tuple(max_x1 - w1, max_y1 - w1, max_x1, max_y1, w1);
cp.points[1] = std::make_tuple(min_x2, max_y2 - w2, min_x2 + w2, max_y2, w2);
cp.width = std::max(w1, w2);
ret = std::min(ret, cp);
}
return ret;
};
auto solve_k2 = [&]() -> Answer {
std::vector<std::pair<i64, i64>> C(N);
for (int i = 0; i < N; ++i) {
C[i] = {X[i], Y[i]};
}
std::sort(C.begin(), C.end());
auto ret = solve_k2sub(N, C);
ret.points[2] = std::make_tuple(-3 * limit, -3 * limit, -3 * limit + 1, -3 * limit + 1, 1);
return ret;
};
auto solve_k3_sub1 = [&]() {
std::vector<std::pair<i64, i64>> C(N);
for (int i = 0; i < N; ++i) {
C[i] = {X[i], Y[i]};
}
std::sort(C.begin(), C.end());
std::vector<i64> max_y_l(N + 1), min_y_l(N + 1);
max_y_l[0] = -inf;
min_y_l[0] = inf;
for (int i = 0; i < N; ++i) {
max_y_l[i + 1] = min_y_l[i + 1] = C[i].second;
}
for (int i = 0; i < N; ++i) {
max_y_l[i + 1] = std::max(max_y_l[i + 1], max_y_l[i]);
min_y_l[i + 1] = std::min(min_y_l[i + 1], min_y_l[i]);
}
auto calc = [&](int m) -> std::pair<Answer, Answer> {
const i64 max_x = C[m - 1].first, min_x = C[0].first;
const i64 max_y = max_y_l[m], min_y = min_y_l[m];
const i64 w = std::max(max_x - min_x, max_y - min_y);
Answer res1;
res1.width = w;
res1.points[0] = std::make_tuple(max_x - w, min_y, max_x, min_y + w, w);
for (int i = m; i < N; ++i) {
C[i] = rotate(C[i].first, C[i].second);
}
std::sort(C.begin() + m, C.end());
auto res2 = solve_k2sub(N - m, std::vector(C.begin() + m, C.end()));
for (int i = m; i < N; ++i) {
C[i] = reverse_rotate(C[i].first, C[i].second);
}
std::sort(C.begin() + m, C.end());
for (int i = 0; i < K; ++i) {
auto &[x1, y1, x2, y2, w] = res2.points[i];
std::tie(x1, y1) = reverse_rotate(x1, y1);
std::tie(x2, y2) = reverse_rotate(x2, y2);
}
return std::make_pair(res1, res2);
};
int ok = 0, ng = N;
Answer ans;
ans.width = inf;
while (std::abs(ok - ng) > 1) {
const auto mid = (ok + ng) / 2;
int real_mid = mid;
while (real_mid != 0 and C[real_mid - 1].first == C[real_mid].first) {
--real_mid;
}
if (real_mid <= ok) {
ok = mid;
continue;
}
auto [res1, res2] = calc(real_mid);
if (res1.width < res2.width) {
ok = mid;
} else {
ng = mid;
}
res2.width = std::max(res1.width, res2.width);
res2.points[2] = res1.points[0];
ans = std::min(ans, res2);
}
return ans;
};
auto solve_k3_sub2 = [&]() {
std::vector<std::pair<i64, i64>> C(N);
for (int i = 0; i < N; ++i) {
C[i] = {X[i], Y[i]};
}
std::sort(C.begin(), C.end());
struct cord {
i64 x;
i64 y_max;
i64 y_min;
};
std::vector<cord> D;
D.push_back({C[0].first, C[0].second, C[0].second});
for (int i = 1; i < N; ++i) {
if (C[i].first == C[i - 1].first) {
D.back().y_max = std::max(D.back().y_max, C[i].second);
D.back().y_min = std::min(D.back().y_min, C[i].second);
} else {
D.push_back({C[i].first, C[i].second, C[i].second});
}
}
const int M = (int)D.size();
auto judge = [&](const i64 lw) -> Answer {
std::vector<i64> max_y_l(M + 1), min_y_l(M + 1), max_y_r(M + 1), min_y_r(M + 1);
max_y_l[0] = max_y_r[M] = -inf;
min_y_l[0] = min_y_r[M] = inf;
for (int i = 0; i < M; ++i) {
max_y_l[i + 1] = D[i].y_max;
min_y_l[i + 1] = D[i].y_min;
max_y_r[i] = D[i].y_max;
min_y_r[i] = D[i].y_min;
}
for (int i = 0; i < M; ++i) {
max_y_l[i + 1] = std::max(max_y_l[i + 1], max_y_l[i]);
min_y_l[i + 1] = std::min(min_y_l[i + 1], min_y_l[i]);
}
for (int i = M; i > 0; --i) {
max_y_r[i - 1] = std::max(max_y_r[i - 1], max_y_r[i]);
min_y_r[i - 1] = std::min(min_y_r[i - 1], min_y_r[i]);
}
int l = M, r = 0;
for (int i = 0; i < M; ++i) {
i64 w = std::max(max_y_l[i + 1] - min_y_l[i + 1], D[i].x - D[0].x);
if (w > lw) {
l = i;
break;
}
}
for (int i = M - 1; i >= 0; --i) {
i64 w = std::max(max_y_r[i] - min_y_r[i], D[M - 1].x - D[i].x);
if (w > lw) {
r = i + 1;
break;
}
}
if (l == 0 or r == M) {
Answer ret;
ret.width = inf;
return ret;
}
if (l >= r) {
// solve_k2
Answer ret;
ret.width = inf - 1;
return ret;
}
std::vector<i64> ymin(M - r, inf), ymax(M - r, -inf);
for (int i = l; i < M; ++i) {
if (i <= r) {
ymax[0] = std::max(ymax[0], D[i].y_max);
ymin[0] = std::min(ymin[0], D[i].y_min);
} else {
ymax[i - r] = std::max(ymax[i - r - 1], D[i].y_max);
ymin[i - r] = std::min(ymin[i - r - 1], D[i].y_min);
}
}
std::vector<T> seg_init(M - r);
for (int i = r; i < M; ++i) {
seg_init[i - r] = std::make_pair((D[i].x - D[l - 1].x - 2) - (ymax[i - r] - ymin[i - r]), i - r);
}
lazy_segtree seg(seg_init);
int max_er = 0, min_er = 0;
i64 yma = ymax[0], ymi = ymin[0];
for (int i = l - 1; i >= 0; --i) {
auto itr = std::upper_bound(D.begin(), D.end(), cord{D[i + 1].x + lw, 0, 0},
[&](auto &a, auto &b) {
return a.x < b.x;
});
const int ir = itr - D.begin();
if (ir <= r) {
break;
}
const auto prod = seg.fold(0, ir - r);
if (prod.first >= 0) {
const int j = prod.second + r + 1;
if (j == M) {
Answer res;
res.width = inf - 1;
return res;
}
Answer res;
const i64 x_ma_1 = D[i].x, x_mi_1 = D[0].x;
const i64 x_ma_2 = D[j - 1].x, x_mi_2 = D[i + 1].x;
const i64 x_ma_3 = D[M - 1].x, x_mi_3 = D[j].x;
const i64 y_ma_1 = max_y_l[i + 1], y_mi_1 = min_y_l[i + 1];
const i64 y_ma_2 = std::max(ymax[j - r - 1], yma), y_mi_2 = std::min(ymin[j - r - 1], ymi);
const i64 y_ma_3 = max_y_r[j], y_mi_3 = min_y_r[j];
const i64 w1 = std::max({x_ma_1 - x_mi_1, y_ma_1 - y_mi_1, 1ll});
const i64 w2 = std::max({x_ma_2 - x_mi_2, y_ma_2 - y_mi_2, 1ll});
const i64 w3 = std::max({x_ma_3 - x_mi_3, y_ma_3 - y_mi_3, 1ll});
const i64 width = std::max({w1, w2, w3});
assert(width <= lw);
if (w2 > x_mi_3 - x_ma_1 - 2) {
continue;
}
res.width = width;
res.points[0] = std::make_tuple(x_ma_1 - w1, y_mi_1, x_ma_1, y_mi_1 + w1, w1);
res.points[2] = std::make_tuple(x_mi_3, y_mi_3, x_ma_3 + w3, y_mi_3 + w3, w3);
i64 xmi2 = x_ma_1 + 1;
if (xmi2 + w2 < x_ma_2) {
xmi2 = x_ma_2 - w2;
}
res.points[1] = std::make_tuple(xmi2, y_mi_2, xmi2 + w2, y_mi_2 + w2, w2);
return res;
}
if (i == 0) {
break;
}
if (D[i].y_max > yma) {
seg.operate_range(0, max_er, -(D[i].y_max - yma));
while (max_er != M - r and ymax[max_er] < D[i].y_max) {
seg.operate_point(max_er, -(D[i].y_max - ymax[max_er]));
++max_er;
}
}
if (D[i].y_min < ymi) {
seg.operate_range(0, min_er, -(ymi - D[i].y_min));
while (min_er != M - r and ymin[min_er] > D[i].y_min) {
seg.operate_point(min_er, -(ymin[min_er] - D[i].y_min));
++min_er;
}
}
yma = std::max(yma, D[i].y_max);
ymi = std::min(ymi, D[i].y_min);
seg.operate_range(0, M - r, D[i].x - D[i - 1].x);
}
Answer ret;
ret.width = inf;
return ret;
};
i64 ok = 2 * limit, ng = 0;
while (ok - ng > 1) {
const auto mid = (ok + ng) / 2;
const auto res = judge(mid);
if (res.width != inf) {
ok = mid;
} else {
ng = mid;
}
}
return judge(ok);
/*
std::vector<std::vector<i64>> y_max(M, std::vector<i64>(M, -inf)), y_min(M, std::vector<i64>(M, inf));
for (int l = 0; l < M; ++l) {
i64 y_ma = D[l].y_max, y_mi = D[l].y_min;
for (int r = l; r < M; ++r) {
y_ma = std::max(y_ma, D[r].y_max);
y_mi = std::min(y_mi, D[r].y_min);
y_max[l][r] = y_ma;
y_min[l][r] = y_mi;
}
}
Answer ret;
ret.width = inf;
for (int i = 1; i < M; ++i) {
for (int j = i + 1; j < M; ++j) {
Answer res;
const i64 x_ma_1 = D[i - 1].x, x_mi_1 = D[0].x;
const i64 x_ma_2 = D[j - 1].x, x_mi_2 = D[i].x;
const i64 x_ma_3 = D[M - 1].x, x_mi_3 = D[j].x;
const i64 y_ma_1 = y_max[0][i - 1], y_mi_1 = y_min[0][i - 1];
const i64 y_ma_2 = y_max[i][j - 1], y_mi_2 = y_min[i][j - 1];
const i64 y_ma_3 = y_max[j][M - 1], y_mi_3 = y_min[j][M - 1];
const i64 w1 = std::max({x_ma_1 - x_mi_1, y_ma_1 - y_mi_1, 1ll});
const i64 w2 = std::max({x_ma_2 - x_mi_2, y_ma_2 - y_mi_2, 1ll});
const i64 w3 = std::max({x_ma_3 - x_mi_3, y_ma_3 - y_mi_3, 1ll});
const i64 width = std::max({w1, w2, w3});
if (w2 > x_mi_3 - x_ma_1 - 2) {
continue;
}
res.width = width;
if (res.width < ret.width) {
res.points[0] = std::make_tuple(x_ma_1 - w1, y_mi_1, x_ma_1, y_mi_1 + w1, w1);
res.points[2] = std::make_tuple(x_mi_3, y_mi_3, x_ma_3 + w3, y_mi_3 + w3, w3);
i64 xmi2 = x_ma_1 + 1;
if (xmi2 + w2 < x_ma_2) {
xmi2 = x_ma_2 - w2;
}
res.points[1] = std::make_tuple(xmi2, y_mi_2, xmi2 + w2, y_mi_2 + w2, w2);
ret = res;
}
}
}
return ret;
*/
};
auto solve_k3 = [&]() -> Answer {
return std::min(solve_k3_sub1(), solve_k3_sub2());
};
auto solve = [&]() {
if (K == 1) {
return solve_k1();
} else if (K == 2) {
return std::min(solve_k1(), solve_k2());
} else {
return std::min({solve_k1(), solve_k2(), solve_k3()});
}
};
auto rotate_all = [&]() {
for (int i = 0; i < N; ++i) {
std::tie(X[i], Y[i]) = rotate(X[i], Y[i]);
}
};
auto reverse = [&](const i64 x) {
return -x;
};
bool is_reversed = false;
auto reverse_all = [&]() {
for (int i = 0; i < N; ++i) {
X[i] = reverse(X[i]);
}
is_reversed = not is_reversed;
};
auto fix = [&](const Answer ans, const int rotate_count) {
Answer res = ans;
if (is_reversed) {
for (int i = 0; i < K; ++i) {
std::get<0>(res.points[i]) = reverse(std::get<0>(res.points[i]));
std::get<2>(res.points[i]) = reverse(std::get<2>(res.points[i]));
}
}
for (int c = 0; c < rotate_count; ++c) {
for (int i = 0; i < K; ++i) {
auto &[x1, y1, x2, y2, w] = res.points[i];
std::tie(x1, y1) = reverse_rotate(x1, y1);
std::tie(x2, y2) = reverse_rotate(x2, y2);
}
}
for (int i = 0; i < K; ++i) {
auto &[x1, y1, x2, y2, w] = res.points[i];
x1 = std::min(x1, x2);
y1 = std::min(y1, y2);
x2 = w;
}
return res;
};
Answer answer;
answer.width = inf;
for (int i = 0; i < 2; ++i) {
answer = std::min(answer, fix(solve(), i));
reverse_all();
answer = std::min(answer, fix(solve(), i));
reverse_all();
rotate_all();
}
for (int i = 0; i < K; ++i) {
std::cout << std::get<0>(answer.points[i]) << ' ';
std::cout << std::get<1>(answer.points[i]) << ' ';
std::cout << std::max(1ll, std::get<2>(answer.points[i])) << std::endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
296 KB |
Output is correct |
| 4 |
Correct |
1 ms |
296 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
79 ms |
3352 KB |
Output is correct |
| 8 |
Correct |
80 ms |
3372 KB |
Output is correct |
| 9 |
Correct |
78 ms |
3272 KB |
Output is correct |
| 10 |
Correct |
80 ms |
3376 KB |
Output is correct |
| 11 |
Correct |
80 ms |
3280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
296 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
296 KB |
Output is correct |
| 8 |
Correct |
1 ms |
304 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
127 ms |
9668 KB |
Output is correct |
| 11 |
Correct |
130 ms |
9596 KB |
Output is correct |
| 12 |
Correct |
124 ms |
9676 KB |
Output is correct |
| 13 |
Correct |
129 ms |
9656 KB |
Output is correct |
| 14 |
Correct |
125 ms |
9608 KB |
Output is correct |
| 15 |
Correct |
125 ms |
9668 KB |
Output is correct |
| 16 |
Correct |
123 ms |
9588 KB |
Output is correct |
| 17 |
Correct |
109 ms |
8956 KB |
Output is correct |
| 18 |
Correct |
114 ms |
8852 KB |
Output is correct |
| 19 |
Correct |
99 ms |
8108 KB |
Output is correct |
| 20 |
Correct |
109 ms |
8580 KB |
Output is correct |
| 21 |
Correct |
127 ms |
9672 KB |
Output is correct |
| 22 |
Correct |
122 ms |
9596 KB |
Output is correct |
| 23 |
Correct |
123 ms |
9672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Runtime error |
1 ms |
432 KB |
Execution killed with signal 6 |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
448 KB |
Output is correct |
| 2 |
Correct |
15 ms |
468 KB |
Output is correct |
| 3 |
Runtime error |
9 ms |
724 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
692 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
