Cod sursa(job #2685570)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 17 decembrie 2020 11:24:24
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
#define sz(x) static_cast<int>((x).size())
#define pd pair<double,double>
#define x first
#define y second

using namespace std;

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

const double EPS = 1e-12;

bool check(pd O, pd A, pd B) {
    return ((A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y)) < EPS;
}

int main() {
    int N;
    fin >> N;
    vector<pd> a(N);
    for(pd &x : a)
        fin >> x.x >> x.y;
    sort(a.begin(), a.end());
    vector<int> S;
    S.emplace_back(0), S.emplace_back(1);
    vector<bool> viz(N);
    viz[1] = true;
    for(int i = 0, add = 1; i >= 0; i += (add = (i == N - 1 ? -add : add))) {
        if(viz[i])
            continue;
        while(sz(S) > 1 && check(a[S[sz(S) - 2]], a[S.back()], a[i])) {
            viz[S.back()] = false;
            S.pop_back();
        }
        S.emplace_back(i);
        viz[i] = true;
    }
    fout << sz(S) - 1 << '\n' << fixed << setprecision(12);
    for(int i = 0; i < sz(S) - 1; ++i)
        fout << a[S[i]].x << ' ' << a[S[i]].y << '\n';
}