#include <bits/stdc++.h>
#include <fstream>
//#define endl '\n'
#define mod 1000000007
#define INF 9000000000000000
using namespace std;
//ofstream fout("intel.out");
//ifstream fin("intel.in");
const int Max = 1e3;
pair<long long, long long> arr[Max];
int n, k;
long long ans = INF;
int which[Max];
struct square{
long long x, y, l;
};
square solu[3];
bool check(pair<long long, long long> a, pair<long long, long long> b) {
if(a.first >= b.first && a.first <= b.second) return true;
if(a.second >= b.first && a.second <= b.second) return true;
if(b.first >= a.first && b.first <= a.second) return true;
if(b.second >= a.first && b.second <= a.second) return true;
return false;
}
void sol(int siz) {
if(siz == n) {
pair<long long, long long> x1= {-INF,INF}, y1 = {-INF,INF}, x2= {-INF,INF}, y2= {-INF,INF}, x3= {-INF,INF}, y3 = {-INF,INF};
for(int i = 0; i < n; i++) {
// cout << which[i] << ' ';
if(which[i] == 1) {
x1.first = max(x1.first,arr[i].first);
x1.second = min(x1.second,arr[i].first);
y1.first = max(y1.first,arr[i].second);
y1.second = min(y1.second,arr[i].second);
}
else if(which[i] == 2) {
x2.first = max(x2.first,arr[i].first);
x2.second = min(x2.second,arr[i].first);
y2.first = max(y2.first,arr[i].second);
y2.second = min(y2.second,arr[i].second);
}
else {
x3.first = max(x3.first,arr[i].first);
x3.second = min(x3.second,arr[i].first);
y3.first = max(y3.first,arr[i].second);
y3.second = min(y3.second,arr[i].second);
}
}
// cout << endl;
if(x1.second == INF) {
x1.first = -3000000000;
x1.second = -3000000000;
y1.first = -3000000000;
y1.second = -3000000000;
}
if(x2.second == INF) {
x2.first = -2000010000;
x2.second = -2000010000;
y2.first = -2000010000;
y2.second = -2000010000;
}
if(x3.second == INF) {
x3.first = -2000000009;
x3.second = -2000000009;
y3.first = -2000000009;
y3.second = -2000000009;
}
long long dis1 = max(max(abs(x1.first-x1.second),abs(y1.first-y1.second)),1ll);
long long dis2 = max(max(abs(x2.first-x2.second),abs(y2.first-y2.second)),1ll);
long long dis3 = max(max(abs(x3.first-x3.second),abs(y3.first-y3.second)),1ll);
// cout << dis1 << ' ' << dis2 << ' ' << dis3 << 'j' << endl;
if((check({x1.second,x1.second+dis1},{x2.second,x2.second+dis2}) && check({y1.second,y1.second+dis1},{y2.second,y2.second+dis2})) || (check({x1.second,x1.second+dis1},{x3.second,x3.second+dis3}) && check({y1.second,y1.second+dis1},{y3.second,y3.second+dis3})) || (check({x2.second,x2.second+dis2},{x3.second,x3.second+dis3}) && check({y2.second,y2.second+dis2},{y3.second,y3.second+dis3}))) return;
if(ans > max(dis1,max(dis2,dis3))) {
solu[0].x = x1.second; solu[0].y = y1.second; solu[0].l = dis1;
solu[1].x = x2.second; solu[1].y = y2.second; solu[1].l = dis2;
solu[2].x = x3.second; solu[2].y = y3.second; solu[2].l = dis3;
ans = max(dis1,max(dis2,dis3));
}
return;
}
which[siz] = 1;
sol(siz+1);
which[siz] = 2;
sol(siz+1);
which[siz] = 3;
sol(siz+1);
}
int main()
{
ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
cin >> n >> k;
if(k == 1) {
pair<long long, long long> x = {-INF,INF}, y = {-INF,INF};
for(int i = 0; i < n; i++) {
long long a, b; cin >> a >> b;
x.first = max(x.first,a);
x.second = min(x.second,a);
y.first = max(y.first,b);
y.second = min(y.second,b);
}
cout << x.second << ' ' << y.second << ' ' << max(max(abs(x.first-x.second),abs(y.first-y.second)),1ll);
}
else if(n <= 12 && k == 3) {
for(int i = 0; i < n; i++) {
cin >> arr[i].first >> arr[i].second;
}
sol(0);
for(int i = 0; i < 3; i++) {
cout << solu[i].x << ' ' << solu[i].y << ' ' << solu[i].l << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
16 ms |
464 KB |
Output is correct |
| 8 |
Correct |
16 ms |
352 KB |
Output is correct |
| 9 |
Correct |
16 ms |
348 KB |
Output is correct |
| 10 |
Correct |
16 ms |
344 KB |
Output is correct |
| 11 |
Correct |
16 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Incorrect |
4 ms |
348 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 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 |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
