Cod sursa(job #412304)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 5 martie 2010 14:39:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

const int size = 120010;

struct pct
{
    double x,y;
}A[size],P1,rez[size];
int n,poz;

double panta(pct b,pct c)
{
    return (b.x-P1.x)*(c.y-P1.y) - (b.y-P1.y)*(c.x-P1.x)>0;
}
double panta2(pct P1,pct b,pct c)
{
   return (b.x-P1.x)*(c.y-P1.y) - (b.y-P1.y)*(c.x-P1.x)>0;
}

struct cmp
{
    bool operator()(const pct &a,const pct &b)const
    {
        return panta(a,b)>0;
    }
};

void solve()
{
    scanf ("%d",&n);
    P1.y=0x3f3f3f;
    for (int i=0;i<n;i++)
    {
        scanf ("%lf %lf",&A[i].x , &A[i].y);
        if (A[i].y<P1.y || (A[i].y==P1.y && A[i].x<P1.x) )
        {
            P1=A[i];
            poz=i;
        }
    }
    pct aux=A[poz];
    A[poz]=A[0];
    A[0]=aux;
    sort(A+1,A+n,cmp());
    rez[1]=A[0];
    rez[2]=A[1];
    rez[3]=A[2];
    int nr=3;
    for (int i=3;i<n;i++)
    {
        while (nr>2 && panta2(rez[nr],A[i],rez[nr-1])<=0)
            nr--;
        rez[++nr]=A[i];
    }
    printf("%d\n",nr);
    for (int i=1;i<=nr;i++)
        printf("%lf %lf\n",rez[i].x,rez[i].y);
}

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