Cod sursa(job #2685555)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 17 decembrie 2020 10:57:08
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
#define sz(x) static_cast<int>((x).size())
#define cd complex<double>
#define x real()
#define y imag()

using namespace std;

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

bool fcmp(const cd &a, const cd &b) {
    if(a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

double crossP(const cd &a, const cd &b) {
    return (conj(a) * b).y;
}

const double EPS = 1e-12;

int main() {
    int N;
    fin >> N;
    vector<cd> a(N);
    for(int i = 0; i < N; ++i) {
        double X, Y;
        fin >> X >> Y;
        a[i] = {X, Y};
    }
    sort(a.begin(), a.end(), fcmp);
    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 && crossP(a[S.back()], a[i]) < EPS) {
            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';
}