Cod sursa(job #1319065)

Utilizator t.g.g.tt.g.g.t t.g.g.t Data 16 ianuarie 2015 17:28:02
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

struct cel
{
    double x,y;
}a[120005];

bool cmp(cel p1,cel p2)
{
    return (p1.y-a[1].y)*(p2.x-a[1].x)<(p2.y-a[1].y)*(p1.x-a[1].x);
}

int lista[120005];

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

    int n;
    scanf("%d",&n);

    double minimx=2000000000,minimy=2000000000;
    int pos=0;

    for (int i=1;i<=n;++i)
    {
        scanf("%lf %lf",&a[i].x,&a[i].y);
        if (a[i].y<minimy || (a[i].y==minimy && a[i].x<minimx))
        {
            pos=i;
            minimx=a[i].x;
            minimy=a[i].y;
        }
    }

    double t=a[1].x; a[1].x=a[pos].x; a[pos].x=t;
           t=a[1].y; a[1].y=a[pos].y; a[pos].y=t;

    sort(a+2,a+1+n,cmp);


    int num=2;
    lista[1]=1; lista[2]=2;

    int i=3;
    while (i<=n)
    {

        cel p1=a[lista[num-1]],p2=a[lista[num]],p3=a[i];

        while (num>=2 && (p3.y-p1.y)*(p2.x-p1.x)-(p2.y-p1.y)*(p3.x-p1.x)<0)
        {
            --num;
            p1=a[lista[num-1]]; p2=a[lista[num]];
        }

        ++num;
        lista[num]=i;

        ++i;
    }

    printf("%d\n",num);

    for (int i=1;i<=num;++i)
    {
        printf("%.12lf %.12lf\n",a[lista[i]].x,a[lista[i]].y);
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}