Cod sursa(job #2106868)

Utilizator MithrilBratu Andrei Mithril Data 16 ianuarie 2018 13:03:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
#define NMAX 120005

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct Punct{double x,y;};
Punct points[NMAX];
Punct st[NMAX];

inline double determ(const Punct& A, const Punct& B, const Punct& C)
{
    return A.x*B.y + B.x*C.y + A.y*C.x - C.x*B.y - A.x*C.y - B.x*A.y;
}

inline bool cmp(const Punct& p1, const Punct& p2)
{
    return determ(points[1], p1, p2) < 0;
}

int main()
{
    int n;
    double x,y;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>x>>y;
        points[i] = Punct{x,y};
    }

    for(int i=2;i<=n;i++)
    {
        if( (points[i].x < points[1].x ) || (points[i].x == points[1].x && points[i].y < points[1].x) )
        {
            swap(points[1], points[i]);
        }
    }
    sort(points+2, points+n+1, cmp);

    st[1] = points[1];
    st[2] = points[2];
    int head = 2;

    for(int i=3;i<=n;i++)
    {
        while(head > 2 && determ(st[head-1], st[head], points[i]) > 0)
            head--;
        st[++head] = points[i];
    }

    fout << fixed;
    fout << head << '\n';
    for(int i = head; i > 0 ; i--)
    {
        fout << setprecision(9) << st[i].x << ' ' << st[i].y << '\n';
    }

    return 0;
}