Cod sursa(job #926858)

Utilizator muscaTudose Vlad-Adrian musca Data 25 martie 2013 13:32:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct coord
{
    double x,y;
};
coord p[120001],lowlow;
int st[120001];
int n,m,i,j,top;
double ccw(coord a,coord b,coord c)
{
    return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool comp(coord a,coord b)
{
    if(ccw(lowlow,a,b)>0) return true;
    return false;
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    scanf("%lf%lf",&p[1].x,&p[1].y);
    lowlow=p[1];
    for(i=2;i<=n;i++)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if(p[i].y-lowlow.y<0||(fabs(p[i].y-lowlow.y<0)&&p[i].x-lowlow.x<0))
        {
            lowlow=p[i];
            p[i]=p[1];
            p[1]=lowlow;
        }
    }
    sort(p+2,p+n+1,comp);
    st[0]=0;
    st[1]=1;
    top=1;
    i=2;
    while(i<=n)
    {
        if(ccw(p[st[top-1]],p[st[top]],p[i])>0)
        {
            st[++top]=i;
            i++;
        }
        else
            top--;
    }
    printf("%d\n",top);
    for(i=1;i<=top;i++)
        printf("%.6lf %.6lf\n",p[st[i]].x,p[st[i]].y);
    return 0;
}