Cod sursa(job #1166249)

Utilizator lianaliana tucar liana Data 3 aprilie 2014 13:22:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define nmax 120005
#define inf 1000000005
struct punct {double x, y;};
punct v[nmax], st[nmax], o;
long i, n, sf;
double difax, difay, difbx, difby, pa, pb;

void citire()
{
    o.y=inf;    o.x=inf;
    scanf("%ld",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%lf %lf",&v[i].x,&v[i].y);
        if ((v[i].x<o.x)||((v[i].x==o.x)&&(v[i].y<o.y)))
            {o=v[i];    v[i]=v[1];  v[1]=o; }
    }
}

bool cmp(punct a, punct b)
{
    difay=a.y-o.y;  difax=a.x-o.x;
    difby=b.y-o.y;  difbx=b.x-o.x;
    if (difax==0)
        pa=inf;
    else
        pa=difay/difax;
    if (difay==0)
        pa=0;
    if (difbx==0)
        pb=inf;
    else
        pb=difby/difbx;
    if (difby==0)
        pb=0;
    return (pa<pb);
}

void rezolvare()
{
    st[1]=v[1]; st[2]=v[2]; st[3]=v[3];sf=3;
    for (i=4;i<=n;i++)
    {
        while ((sf>=3)&&(st[sf-1].x*st[sf].y + st[sf].x*v[i].y + v[i].x*st[sf-1].y  -  st[sf].y*v[i].x - v[i].y*st[sf-1].x - st[sf-1].y*st[sf].x<0))
            sf--;
        st[++sf]=v[i];
    }
    printf("%ld\n",sf);
    printf("%lf %lf\n",st[1].x,st[1].y);
    for (i=2;i<=sf;i++)
        printf("%lf %lf\n",st[i].x,st[i].y);

}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    sort(v+2,v+1+n,cmp);
    rezolvare();
    return 0;
}