Cod sursa(job #799065)

Utilizator Viva12Ferentz Sergiu Viva12 Data 17 octombrie 2012 20:27:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <cstdio>
#include <stack>
#include <algorithm>
#define N 120005
#define oo 1000000005
using namespace std;

struct punct
{
    double X,Y;
}puncte[N],minPct,sol[N];


int elem;
int n;
void citire()
{
    minPct.X = oo;
    minPct.Y = oo;
    int poz;
    scanf("%d",&n);
    for(int i =0 ; i < n; i++)
    {
        scanf("%lf %lf",&puncte[i].X,&puncte[i].Y);
        if(puncte[i].X < minPct.X || puncte[i].X == minPct.X && puncte[i].Y < minPct.Y)
            {
                minPct = puncte[i];
                poz = i;
            }

    }
    puncte[poz] = puncte[n-1];
    n--;

}

double panta(punct p1,punct p2)
{
    if(p1.X != p2.X)
    return ( (p2.Y - p1.Y) / (p2.X - p1.X) );

    return oo;
}

struct cmp{

    bool operator()(punct p1, punct p2)
    {
        return panta(minPct,p1) < panta(minPct,p2);

    }
};

double sortPanta()
{
    sort(puncte,puncte+n,cmp());
}

/*

x1 y1 1
x2 y2 1
x3 y3 1

*/

double getDeterminate(punct p1, punct p2, punct p3)
{
    return ( (p1.X*p2.Y + p2.X*p3.Y + p1.Y*p3.X) - (p3.X * p2.Y + p2.X * p1.Y + p3.Y * p1.X) ) ;
}

void solve()
{
   elem = 0;
   sol[elem++] = minPct;
   sol[elem++] = puncte[0];

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

       if(getDeterminate(sol[elem-2],sol[elem-1],puncte[i]) >= 0)
          sol[elem++] = puncte[i];

       else
        {
            while(getDeterminate(sol[elem-2],sol[elem-1],puncte[i]) < 0)
                sol[--elem] = puncte[i];
            elem++;
        }
   }

}

void write()
{
    printf("%d\n",elem);
    for(int i = 0;  i < elem ; i ++)
    {
        printf("%lf %lf\n",sol[i].X,sol[i].Y);
    }

}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    sortPanta();
    solve();
    write();
    return 0;
}