Cod sursa(job #1297282)

Utilizator akaprosAna Kapros akapros Data 21 decembrie 2014 21:21:54
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,i,j,p,nr;
struct punct
{
    double x;
    double y;
}q,cp,v[120005],w[120005];
double sp(const punct a,const punct b,const punct c)
{
    return ((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x));
}
double cmp(const punct a,const punct b)
{
    return sp(v[1],a,b)>0;
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    p=1;
    for (i=1;i<=n;i++)
    {
        scanf("%lf %lf",&v[i].x,&v[i].y);
        if (v[i].x<v[p].x) p=i; else
        if ((v[i].x==v[p].x)&&(v[i].y<v[p].y)) p=i;
    }
    q=v[p];  punct aux;
    aux=v[p]; v[p]=v[1]; v[1]=aux;
    sort(v+2,v+n+1,cmp);
    nr=2; w[1]=v[1]; w[2]=v[2];
    for (i=3;i<=n;i++)
    {
        while ((nr>1)&&(sp(w[nr],w[nr-1],v[i])>0)) nr--;
        w[++nr]=v[i];
    }
    printf("%d\n",nr);
    sort(w+1,w+nr+1,cmp);
    for (i=1;i<=nr;i++) printf("%.12lf %.12lf\n",w[i].x,w[i].y);
    return 0;
}