Cod sursa(job #1807367)

Utilizator andrei_uAndrei andrei_u Data 16 noiembrie 2016 13:57:53
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <iomanip>
using namespace std;
ofstream cout("infasuratoare.out");
ifstream cin("infasuratoare.in");
struct point
{
    long double x;
    long double y;
} p[120005],sol[120005];

int a,b,nr,mini,n,x,a1,nrsol,i;

long double arie(point a, point b, point c)
{
    b.x-=a.x;
    b.y-=a.y;
    c.x-=a.x;
    c.y-=a.y;

    return (b.x*c.y-b.y*c.x)/2;
}

int main()
{
    cin>>n;

    for(int i=1; i<=n; ++i)
    {
        cin>>p[i].x>>p[i].y;

        if(i==1)
        {
            mini=p[i].x;
            a=i;
        }

        else
        {
            if(p[i].x<mini)
            {
                mini=p[i].x;
                a=i;
            }

            else if(p[i].x==mini && p[a].y<p[i].y)
            {
                a=i;
            }
        }
    }

    a1=a;
    b=1;

    if(b==a)
    {
        b++;
    }

    do
    {
        for(int i=1; i<=n; ++i)
        {

            if(arie(p[a],p[b],p[i])>0)
            {
                b=i;
            }
        }

        nr++;
        sol[++nrsol].x=p[a].x;
        sol[nrsol].y=p[a].y;

        a=b;

        b=1;

        if(a==b)
        {
            b++;
        }
    }
    while(a1!=a);

    cout<<nr<<"\n";

    for(i=1;i<=nrsol;++i)
        cout<<setprecision(12)<<fixed<<sol[i].x<<" "<<sol[i].y<<"\n";

    return 0;
}