Cod sursa(job #1113076)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 20 februarie 2014 12:15:04
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int N, top=2, pmin=1;
struct pct{ double x, y; }v[120002], st[120002], aux;

double cprod(const pct &A, const pct &B, const pct &C)
{ return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x); }

inline int cmp(const pct& p1, const pct& p2) { return cprod(v[1], p1, p2) < 0; }

void ConexHull()
{
    st[1]=v[1]; st[2]=v[2];
    for (int i=3; i<=N; ++i)
    {
        while (top>1 && cprod(st[top-1], st[top], v[i])>0)
            --top;
        st[++top]=v[i];
    }
}

int main()
{
    f>>N;
    for (int i=1; i<=N; ++i)
    {
        f>>v[i].x>>v[i].y;
        if (v[pmin].x>v[i].x || (v[pmin].x==v[i].x && v[pmin].y>v[i].y)) pmin=i;
    }
    swap(v[1], v[pmin]);
    sort(v+2, v+N+1, cmp);
    ConexHull();
    g<<fixed<<setprecision(6)<<top<<'\n';
    for (int i=1; i<=top; ++i)
        g<<st[i].x<<' '<<st[i].y<<'\n';
    return 0;
}