Submission #863961

#	Time	Username	Problem	Language	Result	Execution time	Memory
863961		Rifal	Izvanzemaljci (COI21_izvanzemaljci)	C++14	5 / 100	16 ms	464 KiB

izvanzemaljci

#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;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 21
• Subtask 3: 0 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32