Cod sursa(job #2159497)

Utilizator radurotaruRotaru Radu Stefan radurotaru Data 10 martie 2018 23:15:34
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

#define x first
#define y second

typedef pair <double,double> point;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

point v[120001],d[120001];
int r,n;
double orientare(point a,point b,point c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp(point p1, point p2)
{
    return orientare(v[1],p1,p2)<0;
}
void sortare()
{
    int q=1;
    for(int i=2; i<=n; i++)
    {
        if(v[i]<v[q])
            q=i;
    }
    swap(v[1],v[q]);
    sort(v+2,v+n+1,cmp);
}
void convexhull()
{
    sortare();
    d[1]=v[1];
    d[2]=v[2];
    r=2;
    for(int i=3; i<=n; i++)
    {
        while(r>=2 && orientare(d[r-1],d[r],v[i])>0)
            r--;
        d[++r]=v[i];
    }
}
void afisare()
{
    g<<fixed;
    g<<r<<'\n';
    for(int i=r; i>=1; i--)
    {
        g<<setprecision(9)<<d[i].x<<" "<<d[i].y<<'\n';
    }
}
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
    {
        f>>v[i].x>>v[i].y;
    }
    convexhull();
    afisare();
    return 0;
}