Cod sursa(job #390380)

Utilizator irene_mFMI Irina Iancu irene_m Data 3 februarie 2010 17:36:22
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <cstdio>
#include <math.h>
#include <algorithm>
#define MaxN 120024

struct punct{
      double x,y,cos;
}     a[MaxN];

int N,M,min,sol[MaxN];

int cmp(punct x,punct y)
{
      return x.cos>y.cos;
}

void read()
{
      int i;
      punct aux;
      freopen("infasuratoare.in","r",stdin);
      scanf("%d",&N);
      scanf("%lf %lf",&a[1].x,&a[1].y);
      a[1].cos=a[1].x/sqrt(a[1].y*a[1].y+a[i].x*a[i].x);
      min=1;
      for(i=2;i<=N;i++)
      {
            scanf("%lf %lf",&a[i].x,&a[i].y);
            a[i].cos=a[i].x/sqrt(a[i].y*a[i].y+a[i].x*a[i].x);
            if(a[i].x<a[min].x || (a[i].x==a[min].x && a[i].y<a[min].y))
                  min=i;
      }
      aux=a[1]; a[1]=a[min]; a[min]=aux;
}

double delta(punct p1,punct p2,punct p3)
{
      return p1.x*p2.y+p2.x*p3.y+p1.y*p3.x-p3.x*p2.y-p3.y*p1.x-p2.x*p1.y;
}

void scanare()
{
      int i;
      double d;
      sol[1]=1; sol[2]=2; sol[3]=3;
      M=3;
      for(i=4;i<=N;i++)
      {
            d=delta(a[sol[M-1]],a[sol[M]],a[i]);
            while(d<0 && M>=2)
            {
                  M--;
                  d=delta(a[sol[M-1]],a[sol[M]],a[i]);
            }
            sol[++M]=i;
      }
}

void write()
{
      int i;
      freopen("infasuratoare.out","w",stdout);
      printf("%d\n",M);
      for(i=1;i<=M;i++)
            printf("%lf %lf\n",a[sol[i]].x,a[sol[i]].y);
}

int main()
{
      read();
      std::sort(a+2,a+N+1,cmp);
      scanare();
      write();
      return 0;
}