Cod sursa(job #3159133)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 20 octombrie 2023 19:17:38
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
#define MAXN 1200000

using namespace std;

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

double det(
        pair<double, double> a,
        pair<double, double> b,
        pair<double, double> c
        ) {
    return (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
}

pair<double, double> arr[MAXN];
int main() {
    int n;

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

    sort(arr, arr + n);
    int k = 0, st[MAXN];

    for (int i = 0; i < n; i++) {
        while (k > 1 && det(arr[st[k - 2]], arr[st[k - 1]], arr[i]) < 0)
            k--;
        st[k++] = i;
    }
    for (int i = n - 2; i >= 0; i--) {
        while (k > 1 && det(arr[st[k - 2]], arr[st[k - 1]], arr[i]) < 0)
            k--;
        st[k++] = i;
    }

    fout << k - 1 << '\n';
    for (int i = 0; i < k - 1; i++)
        fout << arr[st[i]].first << ' ' << arr[st[i]].second << '\n';
    return 0;
}