Cod sursa(job #411255)

Utilizator irene_mFMI Irina Iancu irene_m Data 4 martie 2010 19:50:26
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.49 kb
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <math.h>
#define infile "infasuratoare.in"
#define outfile "infasuratoare.out"
#define MaxN 120024
#define prec 0.000000000001

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

int N,M;
int s[MaxN];

int cmp(punct A,punct B)
{
      return (A.cos-B.cos>prec || (fabs(A.cos-B.cos)<prec && B.x-A.x>prec) || (fabs(A.cos-B.cos)<prec && fabs(A.x-B.x)<prec && A.y-B.y>prec));
}

void read()
{
      int i,poz;
      punct aux;
      double minx,miny;
      scanf("%d",&N);
      scanf("%lf%lf",&P[1].x,&P[1].y);
      minx=P[1].x; miny=P[1].y; poz=1;
      for(i=2;i<=N;i++)
      {
            scanf("%lf%lf",&P[i].x,&P[i].y);
            if(P[i].y<miny || (P[i].y==miny && P[i].x<minx))
            {
                  minx=P[i].x; miny=P[i].y;
                  poz=i;
            }
      }
      aux=P[1]; P[1]=P[poz]; P[poz]=aux;
}

double dist(punct A,punct B)
{
      return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

void cosinus()
{
      int i;
      for(i=2;i<=N;i++)
            P[i].cos=(P[i].x-P[1].x)/dist(P[i],P[1]);
      std::sort(P+2,P+N+1,cmp);
}

double determinant(punct P1,punct P2,punct P3)
{
      return P1.x*P2.y+P1.y*P3.x+P2.x*P3.y-P3.x*P2.y-P3.y*P1.x-P2.x*P1.y;
}

void dreapta(punct A,punct B,double &a,double &b,double &c)
{
      a=A.y-B.y;
      b=B.x-A.x;
      c=A.x*B.y-B.x*A.y;
}

void elimina_coliniar()
{
      int i,j,k,n=1;
      double a,b,c;
      i=2;
      P2[1]=P[1];
      while(i<=N)
      {
            dreapta(P2[n],P[i],a,b,c);
            k=i;
            while(fabs(a*P[k].x+b*P[k].y+c)<0.0001 && k<=N)
                  k++;
            i=k;
            P2[++n]=P[k-1];
      }
      N=n;
}

void solve()
{
      cosinus();
      elimina_coliniar();
      int i;
      double det;
      M=2; s[1]=1; s[2]=2;
      for(i=3;i<=N;i++)
      {
            det=determinant(P2[s[M-1]],P2[s[M]],P2[i]);
            while(det<0 && M>2)
            {
                  M--;
                  det=determinant(P2[s[M-1]],P2[s[M]],P2[i]);
            }
            s[++M]=i;
      }
}

void write()
{
      int i;
      printf("%d\n",M);
      for(i=1;i<=M;i++)
            printf("%lf %lf\n",P2[s[i]].x,P2[s[i]].y);
}

int main()
{
      freopen(infile,"r",stdin);
      freopen(outfile,"w",stdout);

      read();
      solve();
      write();

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