Cod sursa(job #3159119)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 20 octombrie 2023 18:58:01
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define MAXN 120000

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const double EPS = 0.00001;

struct point {
    double x, y;
};

double det(point a, point b, point c) {
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

int main() {
    int n;
    point arr[MAXN];

    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> arr[i].x >> arr[i].y;

    sort(arr, arr + n, [](point a, point b) {
        if (a.x == b.x)
            return a.y > a.y;
        return a.x < b.x;
    });

    int k = 0;
    int st[MAXN];
    bool c[MAXN];
    memset(c, false, sizeof(c));
    for (int i = 0; i < n; i++) {
        if (c[i]) continue;
        while (k > 1 && det(arr[st[k - 2]], arr[st[k - 1]], arr[i]) < 0) {
            c[st[--k]] = true;
        }
        st[k++] = i;
    }
    for (int i = n - 1; i >= 0; i--) {
        if (c[i]) continue;
        while (k > 1 && det(arr[st[k - 2]], arr[st[k - 1]], arr[i]) < 0) {
            c[st[--k]] = true;
        }
        st[k++] = i;
    }

    fout << k << '\n';
    for (int i = 0; i < k; i++)
        fout << arr[st[i]].x << ' ' << arr[st[i]].y << '\n';
    return 0;
}