#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <random>
#include <deque>
using namespace std;
mt19937 rng(420691273);
#define ll long long
const int MX = 5e3 + 5;
int n, k;
vector<pair<int, int> > v, owo[3];
pair<pair<int, int>, int> get_square(vector<pair<int, int> > pt){
int mxx = pt[0].first, mnx = pt[0].first;
int mxy = pt[0].second, mny = pt[0].second;
for(int i = 1; i < pt.size(); i ++){
mxx = max(mxx, pt[i].first);
mnx = min(mnx, pt[i].first);
mxy = max(mxy, pt[i].second);
mny = min(mny, pt[i].second);
}
int sz = max(1, max(mxx - mnx, mxy - mny));
// check validity
bool ok = 1;
for(int i = 0; i < pt.size(); i ++){
if(pt[i].first < mnx || pt[i].first > mnx + sz || pt[i].second < mny || pt[i].second > mny + sz)
ok = 0;
}
if(ok) return {{mnx, mny}, sz};
else return {{-1, -1}, -1};
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> k;
v.resize(n);
for(int i = 0; i < n; i ++)
cin >> v[i].first >> v[i].second;
if(!(k == 3 && n <= 12) && !(k == 1)) return 0;
int all = 1;
for(int i = 0; i < n; i ++) all *= k;
int mx = 2000 * 1000 * 1000 + 696969;
vector<pair<pair<int, int>, int> > ans;
for(int msk = 0; msk < all; msk ++){
for(int i = 0; i < k; i ++) owo[i].clear();
for(int tmp = msk, i = 0; i < n; i ++, tmp /= k)
owo[tmp % k].push_back(v[i]);
vector<pair<pair<int, int>, int> > get(k);
bool valid = 1; int mx_nw = 0ll;
for(int i = 0; i < k; i ++){
if(owo[i].empty()){
valid = 0; break;
}
get[i] = get_square(owo[i]);
if(get[i].second == -1) valid = 0;
mx_nw = max(mx_nw, get[i].second);
}
if(valid && mx > mx_nw){
mx = mx_nw;
ans = get;
}
}
for(auto i : ans)
cout << i.first.first << " " << i.first.second << " " << i.second << endl;
return 0;
}
Compilation message
izvanzemaljci.cpp: In function 'std::pair<std::pair<int, int>, int> get_square(std::vector<std::pair<int, int> >)':
izvanzemaljci.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i = 1; i < pt.size(); i ++){
| ~~^~~~~~~~~~~
izvanzemaljci.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < pt.size(); i ++){
| ~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
30 ms |
2768 KB |
Output is correct |
8 |
Correct |
51 ms |
2764 KB |
Output is correct |
9 |
Correct |
37 ms |
2752 KB |
Output is correct |
10 |
Correct |
34 ms |
2776 KB |
Output is correct |
11 |
Correct |
30 ms |
2776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Unexpected end of file - int64 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Unexpected end of file - int64 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Unexpected end of file - int64 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Unexpected end of file - int64 expected |
2 |
Halted |
0 ms |
0 KB |
- |