#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;
}
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 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_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());
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) {
if (C[i - 1].first == C[i].first) {
continue;
}
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];
Answer cp;
const i64 w1 = std::max(max_x1 - min_x1, max_y1 - min_y1);
const i64 w2 = std::max(max_x2 - min_x2, max_y2 - min_y2);
cp.points[0] = std::make_tuple(max_x1 - w1, min_y1, max_x1, min_y1 + w1, w1);
cp.points[1] = std::make_tuple(min_x2, min_y2, min_x2 + w2, min_y2 + w2, w2);
cp.width = std::max(w1, w2);
ret = std::min(ret, cp);
}
ret.points[2] = std::make_tuple(-3 * limit, -3 * limit, -3 * limit + 1, -3 * limit + 1, 1);
return ret;
};
auto solve_k3 = [&]() -> Answer {
Answer ret;
return ret;
};
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 = [&](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 rotate_all = [&]() {
for (int i = 0; i < N; ++i) {
std::tie(X[i], Y[i]) = rotate(X[i], Y[i]);
}
};
auto reverse = [&](const i64 y) {
return -y;
};
bool is_reversed = false;
auto reverse_all = [&]() {
for (int i = 0; i < N; ++i) {
Y[i] = reverse(Y[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<1>(res.points[i]) = reverse(std::get<1>(res.points[i]));
std::get<3>(res.points[i]) = reverse(std::get<3>(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);
std::get<2>(res.points[i]) = std::get<4>(res.points[i]);
}
return res;
};
Answer answer;
answer.width = inf;
for (int i = 0; i < 4; ++i) {
if (i == 1) {
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 |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
79 ms |
2384 KB |
Output is correct |
| 8 |
Correct |
82 ms |
2320 KB |
Output is correct |
| 9 |
Correct |
78 ms |
2288 KB |
Output is correct |
| 10 |
Correct |
77 ms |
2468 KB |
Output is correct |
| 11 |
Correct |
75 ms |
2368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
