#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define fi first #define se second #define vi vector<int> #define vll vector<long long> #define pii pair<int, int> #define pll pair<long long, long long> #define pb push_back #define mp make_pair #define eb emplace_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count()); inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);} inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);} #ifdef DEBUG auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";} #define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X) #else #define debug(...){} #endif #define int long long struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; struct pair_hash{ size_t operator()(const pair<int,int>&x)const{ return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32)); } }; const int INF = 2e9 + 7; struct Area{ int mxX, mnX, mxY, mnY; Area(){ mxX = mxY = -INF; mnX = mnY = INF; } Area(int a, int b, int c, int d){ mxX = a; mnX = b; mxY = c; mnY = d; } Area(int x, int y){ mxX = mnX = x; mxY = mnY = y; } }; Area merge(Area a, Area b){ return Area(max(a.mxX, b.mxX), min(a.mnX, b.mnX), max(a.mxY, b.mxY), min(a.mnY, b.mnY)); } int sideLen(Area x){ return max({1LL, x.mxX - x.mnX, x.mxY - x.mnY}); } bool comp(pii& x, pii& y){ if(x.se != y.se){ return x.se < y.se; } return x.fi < y.fi; } // [x.mxX]: 81; // [x.mnX]: -53; // [x.mxY]: -74; // [x.mnY]: -94; // ------ // [x.mxX]: 55; // [x.mnX]: -97; // [x.mxY]: 72; // [x.mnY]: -73; // ------ // [x.mxX]: 45; // [x.mnX]: -99; // [x.mxY]: 100; // [x.mnY]: 93; vector<Area> squares; //{Area(81, -53, -74, -94), Area(55, -97, 72, -73), Area(45, -99, 100, 93)}; bool disjoint(Area a, Area b){ if(a.mxX < b.mnX || b.mxX < a.mnX || a.mxY < b.mnY || b.mxY < a.mnY){ return true; } return false; } void display(Area x){ cerr << "------\n"; debug(x.mxX); debug(x.mnX); debug(x.mxY); debug(x.mnY); } bool validateAndCheckDisjoint(int L){ for(int i = 0; i < sz(squares); i++){ if(sideLen(squares[i]) > L){ return false; } for(int j = i + 1; j < sz(squares); j++){ if(!disjoint(squares[i], squares[j])){ return false; } } } int special = -1; for(int i = 0; i < sz(squares); i++){ bool up = false; bool down = false; bool l = false; bool r = false; for(int j = 0; j < sz(squares); j++){ if(i == j){ continue; } if(squares[j].mxX < squares[i].mnX){ l = true; }else if(squares[j].mnX > squares[i].mxX){ r = true; }else if(squares[j].mxY < squares[i].mnY){ down = true; }else if(squares[j].mnY > squares[i].mxY){ up = true; } if((up && down) || (l && r)){ special = i; } } } if(special != -1){ swap(squares[0], squares[special]); for(int i = 0; i < 1; i++){ int lx = squares[i].mxX - sideLen(squares[i]); for(int j = 0; j < sz(squares); j++){ if(i != j && squares[j].mxX < squares[i].mnX){ int pre = squares[i].mnX; squares[i].mnX = squares[j].mxX; if(!disjoint(squares[i], squares[j])){ lx = max(lx, squares[j].mxX + 1); } squares[i].mnX = pre; } } squares[i].mnX = lx; int px = squares[i].mnX + sideLen(squares[i]); for(int j = 0; j < sz(squares); j++){ if(i != j && squares[j].mnX > squares[i].mxX){ int pre = squares[i].mxX; squares[i].mxX = squares[j].mnX; if(!disjoint(squares[i], squares[j])){ px = min(px, squares[j].mnX - 1); } squares[i].mxX = pre; } } squares[i].mxX = px; int ly = squares[i].mxY - sideLen(squares[i]); for(int j = 0; j < sz(squares); j++){ if(i != j && squares[j].mxY < squares[i].mnY){ int pre = squares[i].mnY; squares[i].mnY = squares[j].mxY; if(!disjoint(squares[i], squares[j])){ ly = max(ly, squares[j].mxY + 1); } squares[i].mnY = pre; } } squares[i].mnY = ly; int py = squares[i].mnY + sideLen(squares[i]); for(int j = 0; j < sz(squares); j++){ if(i != j && squares[j].mnY > squares[i].mxY){ int pre = squares[i].mxY; squares[i].mxY = squares[j].mnY; if(!disjoint(squares[i], squares[j])){ py = min(py, squares[j].mnY - 1); } squares[i].mxY = pre; } } squares[i].mxY = py; } for(int i = 1; i < sz(squares); i++){ int lx = squares[i].mxX - sideLen(squares[i]); for(int j = 0; j < sz(squares); j++){ if(i != j && squares[j].mxX < squares[i].mnX){ int pre = squares[i].mnX; squares[i].mnX = squares[j].mxX; if(!disjoint(squares[i], squares[j])){ lx = max(lx, squares[j].mxX + 1); } squares[i].mnX = pre; } } squares[i].mnX = lx; } for(int i = 1; i < sz(squares); i++){ int px = squares[i].mnX + sideLen(squares[i]); for(int j = 0; j < sz(squares); j++){ if(i != j && squares[j].mnX > squares[i].mxX){ int pre = squares[i].mxX; squares[i].mxX = squares[j].mnX; if(!disjoint(squares[i], squares[j])){ px = min(px, squares[j].mnX - 1); } squares[i].mxX = pre; } } squares[i].mxX = px; } for(int i = 1; i < sz(squares); i++){ int ly = squares[i].mxY - sideLen(squares[i]); for(int j = 0; j < sz(squares); j++){ if(i != j && squares[j].mxY < squares[i].mnY){ int pre = squares[i].mnY; squares[i].mnY = squares[j].mxY; if(!disjoint(squares[i], squares[j])){ ly = max(ly, squares[j].mxY + 1); } squares[i].mnY = pre; } } squares[i].mnY = ly; } for(int i = 1; i < sz(squares); i++){ int py = squares[i].mnY + sideLen(squares[i]); for(int j = 0; j < sz(squares); j++){ if(i != j && squares[j].mnY > squares[i].mxY){ int pre = squares[i].mxY; squares[i].mxY = squares[j].mnY; if(!disjoint(squares[i], squares[j])){ py = min(py, squares[j].mnY - 1); } squares[i].mxY = pre; } } squares[i].mxY = py; } for(int i = 0; i < sz(squares); i++){ if(squares[i].mxX - squares[i].mnX != squares[i].mxY - squares[i].mnY){ return false; } for(int j = i + 1; j < sz(squares); j++){ if(!disjoint(squares[i], squares[j])){ return false; } } } return true; }else{ for(int i = 0; i < sz(squares); i++){ int lx = squares[i].mxX - sideLen(squares[i]); for(int j = 0; j < sz(squares); j++){ if(i != j && squares[j].mxX < squares[i].mnX){ int pre = squares[i].mnX; squares[i].mnX = squares[j].mxX; if(!disjoint(squares[i], squares[j])){ lx = max(lx, squares[j].mxX + 1); } squares[i].mnX = pre; } } squares[i].mnX = lx; } for(int i = 0; i < sz(squares); i++){ int px = squares[i].mnX + sideLen(squares[i]); for(int j = 0; j < sz(squares); j++){ if(i != j && squares[j].mnX > squares[i].mxX){ int pre = squares[i].mxX; squares[i].mxX = squares[j].mnX; if(!disjoint(squares[i], squares[j])){ px = min(px, squares[j].mnX - 1); } squares[i].mxX = pre; } } squares[i].mxX = px; } for(int i = 0; i < sz(squares); i++){ int ly = squares[i].mxY - sideLen(squares[i]); for(int j = 0; j < sz(squares); j++){ if(i != j && squares[j].mxY < squares[i].mnY){ int pre = squares[i].mnY; squares[i].mnY = squares[j].mxY; if(!disjoint(squares[i], squares[j])){ ly = max(ly, squares[j].mxY + 1); } squares[i].mnY = pre; } } squares[i].mnY = ly; } for(int i = 0; i < sz(squares); i++){ int py = squares[i].mnY + sideLen(squares[i]); for(int j = 0; j < sz(squares); j++){ if(i != j && squares[j].mnY > squares[i].mxY){ int pre = squares[i].mxY; squares[i].mxY = squares[j].mnY; if(!disjoint(squares[i], squares[j])){ py = min(py, squares[j].mnY - 1); } squares[i].mxY = pre; } } squares[i].mxY = py; } for(int i = 0; i < sz(squares); i++){ if(squares[i].mxX - squares[i].mnX != squares[i].mxY - squares[i].mnY){ return false; } for(int j = i + 1; j < sz(squares); j++){ if(!disjoint(squares[i], squares[j])){ return false; } } } return true; } } vector<pair<pii, int>> changeToSquares(){ vector<pair<pii, int>> res = {}; for(auto ele : squares){ res.pb(mp(mp(ele.mnX, ele.mnY), sideLen(ele))); } return res; } void solve(vector<pii> a, int n, int k, int L){ if(k == 1){ if(sz(a) == 0){ Area now = Area(INF, INF); squares.pb(now); return; } // debug(a); Area now = Area(a[0].fi, a[0].se); for(int i = 1; i < sz(a); i++){ now = merge(now, Area(a[i].fi, a[i].se)); } // display(now); squares.pb(now); // cerr << "-----\n"; // cerr << "POLA\n"; // for(auto ele : squares){ // display(ele); // } // cout << validateAndCheckDisjoint(L) << '\n'; return; } if(k == 2){ if(sz(a) == 0){ Area now = Area(-INF, -INF); squares.pb(now); solve(a, sz(a), k - 1, L); return; } // debug(a); for(int xd = 0;xd < 2; xd++){ // debug(a); // debug(xd); Area now = Area(a[0].fi, a[0].se); vector<pii> na = {}; bool zle = false; int i = 1; while(i < sz(a)){ int pocz = i; Area now2 = now; while(i + 1 < sz(a)){ if(xd == 0){ if(a[i + 1].se != a[i].se){ break; } }else{ if(a[i + 1].fi != a[i].fi){ break; } } i++; } for(int j = pocz; j <= i; j++){ now2 = merge(now2, Area(a[j].fi, a[j].se)); } if(!zle && sideLen(now2) <= L && (sz(squares) == 0 || disjoint(now2, squares[0]))){ now = now2; }else{ zle = true; for(int j = pocz; j <= i; j++){ na.pb(a[j]); } } i++; } // debug(na); // display(now); squares.pb(now); solve(na, sz(na), k - 1, L); if(validateAndCheckDisjoint(L)){ //cerr << "PASSED\n"; return; } // cerr << "NOT PASSES\n"; if(xd){ break; } squares.pop_back(); squares.pop_back(); sort(all(a)); } return; } // debug(a); Area now = Area(a[0].fi, a[0].se); vector<pii> na = {}; bool zle = false; int i = 1; while(i < sz(a)){ int pocz = i; while(i + 1 < sz(a) && a[i + 1].se == a[pocz].se){ i++; } Area now2 = now; for(int j = pocz; j <= i; j++){ now2 = merge(now2, Area(a[j].fi, a[j].se)); } if(!zle && sideLen(now2) <= L){ now = now2; }else{ zle = true; for(int j = pocz; j <= i; j++){ na.pb(a[j]); } } i++; } //display(now); squares.pb(now); solve(na, sz(na), k - 1, L); } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // cout << validateAndCheckDisjoint(152) << '\n'; // return 0; int n, k; cin >> n >> k; // cout << n << ' ' << k << '\n'; vector<pii> a(n); for(int i = 0; i < n; i++){ cin >> a[i].fi >> a[i].se; //cout << a[i].fi << ' ' << a[i].se << '\n'; } if(n < k){ sort(all(a)); if(n == 1){ vector<pair<pii, int>> res = {mp(a[0], 1)}; for(int j = 2; j <= k; j++){ int x = (j == 2 ? (int)1e9 : (int)-1e9); res.pb(mp(mp(x, 0), 1)); } for(auto ele : res){ cout << ele.fi.fi << ' ' << ele.fi.se << ' ' << ele.se << '\n'; } }else if(n == 2){ vector<pair<pii, int>> res = {mp(mp(a[0].fi - 1, a[0].se - 1), 1), mp(a[1],1)}; if(k == 3){ res.pb(mp(mp(INF, INF), 1)); } for(auto ele : res){ cout << ele.fi.fi << ' ' << ele.fi.se << ' ' << ele.se << '\n'; } } return 0; } vector<pii> pocz = a; int l = 1; int p = INF; int mid; vector<pair<pii, int>> res; int best = 2 * INF; int nbest; while(l < p){ mid = (l + p) / 2; // cerr << "MID: " << mid << '\n'; bool f = false; for(int i1 = 0; i1 < 2; i1++){ for(int i2 = 0; i2 < 2; i2++){ if(f){ break; } squares.clear(); vector<pii> na = pocz; nbest = 0; if(i1 && !i2){ for(auto& ele : na){ swap(ele.fi, ele.se); } // cerr << "POCZĄTEK INTERESUJĄCEJ CZĘŚCI Z swapem\n"; sort(all(na), comp); solve(na, n, k, mid); if(validateAndCheckDisjoint(mid)){ for(auto& ele : squares){ nbest = max(nbest, sideLen(ele)); swap(ele.mnX, ele.mnY); swap(ele.mxX, ele.mxY); } if(nbest < best){ res = changeToSquares(); } f = true; } }else if(i2 && !i1){ for(auto& ele : na){ ele.se = -ele.se; } sort(all(na), comp); solve(na, n, k, mid); if(validateAndCheckDisjoint(mid)){ for(auto& ele : squares){ int pre = ele.mnY; ele.mnY = -ele.mxY; ele.mxY = -pre; nbest = max(nbest, sideLen(ele)); } if(nbest < best){ res = changeToSquares(); } f = true; } }else if(i2 && i1){ for(auto& ele : na){ swap(ele.fi, ele.se); ele.se = -ele.se; } sort(all(na), comp); solve(na, n, k, mid); if(validateAndCheckDisjoint(mid)){ for(auto& ele : squares){ int pre = ele.mnY; ele.mnY = -ele.mxY; ele.mxY = -pre; swap(ele.mnX, ele.mnY); swap(ele.mxX, ele.mxY); nbest = max(nbest, sideLen(ele)); } if(nbest < best){ res = changeToSquares(); } f = true; } }else{ sort(all(na), comp); solve(na, n, k, mid); if(validateAndCheckDisjoint(mid)){ for(auto& ele : squares){ nbest = max(nbest, sideLen(ele)); } if(nbest < best){ res = changeToSquares(); } f = true; } } } if(f){ break; } } if(f){ p = mid; }else{ l = mid + 1; } } for(auto ele : res){ cout << ele.fi.fi << ' ' << ele.fi.se << ' ' << ele.se << '\n'; } return 0; }