Cod sursa(job #2263025)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 18 octombrie 2018 00:16:20
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>

#define point std::pair <double, double>
#define x     first
#define y     second
#define MaxN  120005

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) {
    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[1], P1, P2) < 0;
}

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[1]);
    Stack.push_back(V[2]);

    for (int i=2; i<N; ++i) {
        while (Stack.size()>1
               && CrossProduct(Stack[Stack.size()-2], Stack[Stack.size()-1], V[i]) > 0)
            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].x << ' ' << Stack[i].y << '\n';
}


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

    return 0;
}