Cod sursa(job #884822)

Utilizator TodeaDariustodea darius TodeaDarius Data 21 februarie 2013 13:01:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,p,nr,k;
double cpx,cpy,pan;
struct coord
{
    double x;
    double y;
} v[120005];
struct panta
{
    double m;
    double mx;
    double my;
} a[120005];
struct stiva
{
    double xstv;
    double ystv;
} stv[120005];
bool cmp(panta b,panta c)
{
    return(b.m<c.m);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&n);
    cpx=cpy=1000000005;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&v[i].x,&v[i].y);
        if(v[i].x<cpx)
        {
            cpx=v[i].x;
            cpy=v[i].y;
            p=i;
        }
        else
        if(v[i].x==cpx && v[i].y<cpy)
        {
            cpy=v[i].y;
            p=i;
        }
    }
    nr=0;
    for(int i=1;i<=n;i++)
    {
        if(i!=p)
        {
            pan=(v[i].y-cpy)/(v[i].x-cpx);
            a[++nr].m=pan;
            a[nr].mx=v[i].x;
            a[nr].my=v[i].y;
        }
    }
    sort(a+1,a+n,cmp);
    for(int i=1;i<n;i++)
    {
        while(k>=2 && ((stv[k].xstv-stv[k-1].xstv)*(a[i].my-stv[k-1].ystv)-(stv[k].ystv-stv[k-1].ystv)*(a[i].mx-stv[k-1].xstv)) <0 )
            k--;
        stv[++k].xstv=a[i].mx;
        stv[k].ystv=a[i].my;
    }
    while(k>=2 && ((stv[k].xstv-stv[k-1].xstv)*(cpy-stv[k-1].ystv)-(stv[k].ystv-stv[k-1].ystv)*(cpx-stv[k-1].xstv)) <0 )
        k--;
    stv[++k].xstv=cpx;
    stv[k].ystv=cpy;
    printf("%d\n",k);
    for(int i=1;i<=k;i++)
        printf("%.6lf %.6lf\n",stv[i].xstv,stv[i].ystv);
        return 0;

}