제출 #420781

#제출 시각아이디문제언어결과실행 시간메모리
420781JvThunderIzvanzemaljci (COI21_izvanzemaljci)C++14
5 / 100
3080 ms1484 KiB
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define fir first #define sec second typedef long long ll; using namespace std; int n,k; struct Node { int x,y,l; }; bool overlap(Node a,Node b) { if(a.x>b.x) swap(a,b); if(b.x<a.x+a.l && a.x+a.l<b.x+b.l) { if(b.y<a.y+a.l && a.y+a.l<b.y+b.l) return true; else return false; } else return false; } pair<pair<Node,Node>,Node> ans; int mnl = 1e9; vector<pair<int,int>> v; vector<pair<int,int>> g[3]; void compute() { Node a[3]; for(int i=0;i<3;i++) { int mnx = 1; int mxx = 1; int mny = 1; int mxy = 1; bool isfir = true; for(auto c:g[i]) { int x = c.fir; int y = c.sec; if(isfir) { isfir = false; mnx = mxx = x; mny = mxy = y; } else { mnx = min(mnx,x); mxx = max(mxx,x); mny = min(mny,y); mxy = max(mxy,y); } } a[i].x = mnx; a[i].y = mny; a[i].l = max(max(mxx-mnx,mxy-mny),1); } if(overlap(a[0],a[1])==true || overlap(a[2],a[1])==true || overlap(a[0],a[2])==true) return; if(max(max(a[0].l,a[1].l),a[2].l) <= mnl) { mnl = max(max(a[0].l,a[1].l),a[2].l); ans = {{a[0],a[1]},a[2]}; return; } } void bf(int curr) { if(curr==n) { compute(); return; } for(int i=0;i<3;i++) { g[i].push_back(v[curr]); bf(curr+1); g[i].pop_back(); } } void solve() { cin >> n >> k; int mnx = 0; int mxx = 0; int mny = 0; int mxy = 0; for(int i=0;i<n;i++) { int x,y; cin >> x >> y; if(i==0) { mnx = mxx = x; mny = mxy = y; } else { mnx = min(mnx,x); mxx = max(mxx,x); mny = min(mny,y); mxy = max(mxy,y); } v.pb({x,y}); } if(k==1) { cout << mnx << " " << mny << " " << max(max(mxx-mnx,mxy-mny),1) << endl; return; } bf(0); cout << ans.fir.fir.x << " " << ans.fir.fir.y << " " << ans.fir.fir.l << endl; cout << ans.fir.sec.x << " " << ans.fir.sec.y << " " << ans.fir.sec.l << endl; cout << ans.sec.x << " " << ans.sec.y << " " << ans.sec.l << endl; return; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...