Cod sursa(job #2263037)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 18 octombrie 2018 01:15:38
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

#define point std::pair <double, double>
#define x     first
#define y     second
#define MaxN  120005
#define eps   1e-12

std::ifstream InFile("infasuratoare.in");
std::ofstream OutFile("infasuratoare.out");

std::istream& operator >> (std::istream& Stream, point &Pair) {
    return Stream >> Pair.first >> Pair.second;
}
inline double CrossProduct(point A, point B, point C) {     // in modul e distanta pct C la dreapta AB .. cred
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

int N;
point V[MaxN];
std::vector <point> Stack;

inline bool cmp(point P1, point P2) {
    return CrossProduct(V[0], P1, P2) <= eps;
}

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]);

    std::sort(V+1, V+N, cmp);
}
void ConvexHull() {
    Sortare();

    Stack.push_back(V[0]);
    Stack.push_back(V[1]);

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

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

void Rezolvare() {
    ConvexHull();

    OutFile << Stack.size() << "\n";
    OutFile << std::fixed << std::setprecision(6);
    for (int i=Stack.size(); i>0; --i)
        OutFile << Stack[i-1].x << ' ' << Stack[i-1].y << '\n';
}


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

    return 0;
}