Cod sursa(job #278816)

Utilizator mihai0110Bivol Mihai mihai0110 Data 12 martie 2009 15:36:50
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<stdio.h>
#include<algorithm>
#define MAXN 120000

using namespace std;

struct punct{double x,y;};
int n,i,j;
punct stiva[MAXN];
punct v[MAXN],mn,aux;

double pvect(double x1, double y1, double x2, double y2, double x3, double y3){
    return ((double)(x1*y2 + x2*y3 + x3*y1) > (double)(x3*y2 + y3*x1 + x2*y1));
}

bool cmp(const punct &b,const punct &a)
{
    return pvect(a.x, a.y, mn.x, mn.y, b.x, b.y);
}

int main(void)
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    mn.x=1000000000;
    mn.y=1000000000;
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&v[i].x,&v[i].y);
        if(v[i].x<mn.x || (v[i].x==mn.x && v[i].y<mn.y))
        {
            mn=v[i];
            j=i;
        }
    }
    aux=v[j];
    v[j]=v[n];
    v[n]=aux;

    sort(v+1,v+n,cmp);

    stiva[0]=mn;
    stiva[1]=v[1];
    int u=2;
    for (i = 2; i <= n; i++)
    {
        while (!pvect(stiva[u-2].x, stiva[u-2].y, stiva[u-1].x, stiva[u-1].y, v[i].x, v[i].y)) u--;
        stiva[u++] = v[i];
    }
    u--;
    printf("%d\n",u);
    for(i=0;i<u;i++)
        printf("%.6lf %.6lf\n",stiva[i].x,stiva[i].y);
    return 0;
}