Submission #681689

#	Time	Username	Problem	Language	Result	Execution time	Memory
681689		qwerasdfzxcl	Izvanzemaljci (COI21_izvanzemaljci)	C++17	0 / 100	1 ms	340 KiB

izvanzemaljci

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Square{
    int l, x, y;
    Square(){}
    Square(int _l, int _x, int _y): l(_l), x(_x), y(_y) {}

    void print(){printf("%d %d %d\n", x, y, l);}
};
pair<int, int> a[100100];
int mn[100100], mx[100100];

void solve1(int n){
    sort(a+1, a+n+1);
    int y1 = a[1].second, y2 = a[1].second;
    for (int i=1;i<=n;i++){
        y1 = min(y1, a[i].second);
        y2 = max(y2, a[i].second);
    }

    Square ans(max(a[n].first-a[1].first, y2-y1), a[1].first, y1);
    ans.print();
}

pair<int, pair<Square, Square>> solve2x(int n){
    sort(a+1, a+n+1);
    a[n+1].first = 1e9;
    mn[n] = a[n].second;
    mx[n] = a[n].second;
    for (int i=n-1;i>0;i--){
        mn[i] = min(mn[i+1], a[i].second);
        mx[i] = max(mx[i+1], a[i].second);
    }

    int y1 = 1e9, y2 = -1e9, ans = 1e9;
    pair<Square, Square> ret;
    for (int i=1;i<=n;i++){
        y1 = min(y1, a[i].second);
        y2 = max(y2, a[i].second);

        int L1 = max(y2-y1, a[i].first-a[1].first);
        int L2 = max(mx[i+1]-mn[i+1], a[n].first-a[i+1].first);

        if (ans > max(L1, L2)){
            ans = max(L1, L2);
            ret = make_pair(Square(L1, a[i].first-L1, y1), Square(L2, a[i+1].first, mn[i+1]));
        }
    }

    return {ans, ret};
}

void solve2(int n){
    auto [ans1, p1] = solve2x(n);
    for (int i=1;i<=n;i++) swap(a[i].first, a[i].second);
    auto [ans2, p2] = solve2x(n);

    auto p = p1;
    if (ans2 < ans1){
        p = p2;
        swap(p.first.x, p.first.y);
        swap(p.second.x, p.second.y);
    }

    p.first.print();
    p.second.print();
}

void solve3(int n){

}

int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i=1;i<=n;i++) scanf("%d %d", &a[i].first, &a[i].second);
    if (k==1) solve1(n);
    if (k==2) solve2(n);
    if (k==3) solve3(n);
    return 0;
}

Compilation message (stderr)

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:78:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     for (int i=1;i<=n;i++) scanf("%d %d", &a[i].first, &a[i].second);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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