#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 10;
void solve1(int N, int K)
{
int x11 = INF, x12 = -INF, y11 = INF, y12 = -INF;
for (int i = 0; i < N; i++)
{
int X, Y;
cin >> X >> Y;
x11 = min(x11, X);
x12 = max(x12, X);
y11 = min(y11, Y);
y12 = max(y12, Y);
}
int l = max(x12 - x11, y12 - y11);
cout << x11 << " " << y11 << " " << l << '\n';
}
void solve2(int N, int K)
{
}
void bt(int id, tuple<int, int, int, int> q1, tuple<int, int, int, int> q2, tuple<int, int, int, int> q3, int &resp, vector<tuple<int, int, int>> &ans, const vector<pair<int, int>> &v)
{
if (id == v.size())
{
auto [x11, x12, y11, y12] = q1;
auto [x21, x22, y21, y22] = q2;
auto [x31, x32, y31, y32] = q3;
if (x11 > x12) x11 = -INF, x12 = -INF+1, y11 = -INF, y12 = -INF+1;
if (x21 > x22) x21 = INF, x22 = INF+1, y21 = -INF, y22 = -INF+1;
if (x31 > x32) x31 = INF, x32 = INF+1, y31 = INF, y32 = INF+1;
int l1 = max(x12 - x11, y12 - y11); x12 = x11 + l1, y12 = y11 + l1;
int l2 = max(x22 - x21, y22 - y21); x22 = x21 + l2, y22 = y21 + l2;
int l3 = max(x32 - x31, y32 - y31); x32 = x31 + l3, y32 = y31 + l3;
if (max({l1, l2, l3}) > resp) return;
bool interX12 = (min(x11, x21) <= max(x11, x21) && max(x11, x21) <= min(x12, x22)) || (min(x11, x21) <= min(x12, x22) && min(x12, x22) <= max(x11, x21));
bool interX13 = (min(x11, x31) <= max(x11, x31) && max(x11, x31) <= min(x12, x32)) || (min(x11, x31) <= min(x12, x32) && min(x12, x32) <= max(x11, x31));
bool interX23 = (min(x21, x31) <= max(x21, x31) && max(x21, x31) <= min(x21, x32)) || (min(x21, x31) <= min(x22, x32) && min(x22, x32) <= max(x21, x31));
bool interY12 = (min(y11, y21) <= max(y11, x21) && max(y11, y21) <= min(y12, x22)) || (min(y11, y21) <= min(y12, y22) && min(y12, y22) <= max(y11, y21));
bool interY13 = (min(y11, y31) <= max(y11, x31) && max(y11, y31) <= min(y12, x32)) || (min(y11, y31) <= min(y12, y32) && min(y12, y32) <= max(y11, y31));
bool interY23 = (min(y21, y31) <= max(y21, x31) && max(y21, y31) <= min(y21, x32)) || (min(y21, y31) <= min(y22, y32) && min(y22, y32) <= max(y21, y31));
if (interX12 && interY12) return;
if (interX13 && interY13) return;
if (interX23 && interY23) return;
resp = max({l1, l2, l3});
ans[0] = make_tuple(x11, y11, l1);
ans[1] = make_tuple(x21, y21, l2);
ans[2] = make_tuple(x31, y31, l3);
return;
}
auto [x11, x12, y11, y12] = q1;
auto [x21, x22, y21, y22] = q2;
auto [x31, x32, y31, y32] = q3;
auto [X, Y] = v[id];
bt(id+1, make_tuple(min(x11, X), max(x12, X), min(y11, Y), max(y12, Y)), q2, q3, resp, ans, v);
bt(id+1, q1, make_tuple(min(x21, X), max(x22, X), min(y21, Y), max(y22, Y)), q3, resp, ans, v);
bt(id+1, q1, q2, make_tuple(min(x31, X), max(x32, X), min(y31, Y), max(y32, Y)), resp, ans, v);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
cin >> N >> K;
if (K == 1) {solve1(N, K); return 0;}
else if (K == 2) {solve2(N, K); return 0;}
vector<pair<int, int>> v(N); for (auto &[x, y] : v) cin >> x >> y;
int resp = INF; vector<tuple<int, int, int>> ans(3);
bt(0, make_tuple(INF, -INF, INF, -INF), make_tuple(INF, -INF, INF, -INF), make_tuple(INF, -INF, INF, -INF), resp, ans, v);
for (auto x : ans)
cout << get<0>(x) << " " << get<1>(x) << " " << get<2>(x) << '\n';
}
Compilation message
izvanzemaljci.cpp: In function 'void bt(int, std::tuple<int, int, int, int>, std::tuple<int, int, int, int>, std::tuple<int, int, int, int>, int&, std::vector<std::tuple<int, int, int> >&, const std::vector<std::pair<int, int> >&)':
izvanzemaljci.cpp:29:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | if (id == v.size())
| ~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Integer 0 violates the range [1, 2*10^9] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Integer 0 violates the range [1, 2*10^9] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3033 ms |
600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3042 ms |
856 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
