oj.uz

Submission #863955

# Submission time Handle Problem Language Result Execution time Memory
863955 2023-10-21T14:37:03 Z Rifal Izvanzemaljci (COI21_izvanzemaljci) C++14
5 / 100
 21 ms 1932 KB 
#include <bits/stdc++.h>
#include <fstream>
//#define endl '\n'
#define mod 1000000007
#define INF 900000000000000

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++) {

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

        }
        if(x1.second == INF) {
            x1.first = 3000000001;
            x1.second = 3000000001;
            y1.first = 3000000001;
            y1.second = 3000000001;
        }
        if(x2.second == INF) {
            x2.first = 3000000005;
            x2.second = 3000000005;
            y2.first = 3000000005;
            y2.second = 3000000005;
        }
        if(x3.second == INF) {
            x3.first = 3000000009;
            x3.second = 3000000009;
            y3.first = 3000000009;
            y3.second = 3000000009;
        }
        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);
        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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 17 ms 1720 KB Output is correct
8 Correct 17 ms 1616 KB Output is correct
9 Correct 21 ms 1716 KB Output is correct
10 Correct 16 ms 1628 KB Output is correct
11 Correct 21 ms 1932 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Integer 3000000005 violates the range [-3*10^9, 3*10^9]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -