Cod sursa(job #2566543)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 2 martie 2020 21:52:48
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>

#define rational    long double
#define point       std::pair <rational, rational>
#define EPS         1e-10
#define x           first
#define y           second

int N;
std::vector <point> V;
std::vector <int> hull;

rational crossproduct(const point &A, const point &B, const point &C) {
    return (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
}

bool cmp(point &A, point &B) {
    return crossproduct(V[0], A, B) < EPS;
}
void computeHull() {
    int minidx = 0;
    for (int i=1; i<N; ++i)
        if (V[i] < V[minidx])
            minidx = i;
    std:;swap(V[0], V[minidx]);
    std::sort(V.begin()+1, V.end(), cmp);

    hull.push_back(0);
    hull.push_back(1);
    for (int i=2; i<N; ++i) {
        while (hull.size() >= 2 && crossproduct(V[hull[hull.size()-2]], V[hull.back()], V[i]) > EPS)
            hull.pop_back();
        hull.push_back(i);
    }
}

#define FILENAME    std::string("infasuratoare")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

int main()
{
    input >> N;
    V.resize(N);
    for (auto &it:V) input >> it.first >> it.second;
    computeHull();
    output << hull.size() << '\n';
    output << std::fixed << std::setprecision(6);
    for (int i=0; i<hull.size(); ++i)
        output << V[hull[i]].first << ' ' << V[hull[i]].second << '\n';

    return 0;
}