Submission #863961

#TimeUsernameProblemLanguageResultExecution timeMemory
863961RifalIzvanzemaljci (COI21_izvanzemaljci)C++14
5 / 100
16 ms464 KiB
#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 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...