Cod sursa(job #2369410)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 5 martie 2019 23:04:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>

#define ldb long double
#define ldb_pair std::pair <long double, long double>
#define x  first
#define y second

#define eps 1e-12

inline ldb crossproduct(const ldb_pair& p0, const ldb_pair& p1, const ldb_pair& p2) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}

ldb_pair origin;
inline bool cmp(const ldb_pair& p0, const ldb_pair& p1) {
    return crossproduct(origin, p0, p1) < eps;
}

std::istream& operator >> (std::istream& stream, ldb_pair& data) {
    return stream >> data.first >> data.second;
}

#define MAXN 120005

int N;
ldb_pair V[MAXN];

void Sortare() {
    int hullbegin = 0;
    for (int i=1; i<N; ++i)
        if (V[i] < V[hullbegin])
            hullbegin = i;
    std::swap(V[0], V[hullbegin]);

    origin = V[0];
    std::sort(V+1, V+N, cmp);
}

std::vector <int> Stack;
void ConvexHull() {
    Stack.push_back(0);
    Stack.push_back(1);

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

std::ifstream In ("infasuratoare.in");
std::ofstream Out("infasuratoare.out");

void Citire() {
    In >> N;
    for (int i=0; i<N; ++i)
        In >> V[i];
}

void Rezolvare() {
    Sortare();
    ConvexHull();

    Out << Stack.size() << '\n';
    Out << std::fixed << std::setprecision(6);
    for (int i = Stack.size()-1; i>=0; --i)
        Out << V[Stack[i]].first << ' ' << V[Stack[i]].second << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}