Cod sursa(job #263205)

Utilizator petrePajarcu Alexandru-Petrisor petre Data 19 februarie 2009 23:31:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

double x[120001],y[120001];
int puncte[120001],pfin[120001],i,n,ini,j;

bool pv( int i,int j)
 {
  return (double) ( x[i] - x[ini])*( y[j]-y[ini])< (double) (x[j]-x[ini]) * (y[i]-y[ini]);
 }

long double ascutit ( int p1,int p2,int p3)
    {
        return (long double) ( x[p1]*y[p2]-x[p1]*y[p3]+x[p2]*y[p3]-x[p2]*y[p1]+x[p3]*y[p1]-x[p3]*y[p2]);
    }

int main()
{
freopen( "infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&n);

for (i=1;i<=n;++i)
    {
        scanf("%lf %lf",&x[i],&y[i]);
        if ( x[i]<x[ini] ||  x[i]==x[ini] && y[i]<y[ini] )  ini=i;
    }


for (i=1;i<=n;++i)
{
    if (i==ini) continue;
    puncte[++puncte[0]]=i;
}

sort(puncte+1,puncte+puncte[0]+1,pv);

pfin[pfin[0]=1]=ini;

for (i=1;i<=puncte[0];++i)
    {
        if (puncte[i]==ini) continue;
        while (pfin[0]>=2 && ascutit(pfin[pfin[0]-1],pfin[pfin[0]],puncte[i])>0) --pfin[0];
        pfin[++pfin[0]]=puncte[i];
    }
    pfin[++pfin[0]]=ini;
    printf("%d\n",pfin[0]-1);
    reverse(pfin+1,pfin+pfin[0]+1);

    for (i=1;i<pfin[0];++i)
    {
        printf("%lf %lf\n",x[pfin[i]],y[pfin[i]]);
    }
    return(0);
    }