Cod sursa(job #303272)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 9 aprilie 2009 18:24:55
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <stdio.h>
#include <algorithm>
#define N 120010

using namespace std;


struct punct
{
     double x,y;
}p,sir[N];

int ind[N],num,poz,n,m;

double fct(punct a,punct b)
{
     return (a.x-p.x)*(b.y-p.y)-(a.y-p.y)*(b.x-p.x)>0;
}

double fct2(punct p,punct a,punct b)
{
     return (a.x-p.x)*(b.y-p.y)-(a.y-p.y)*(b.x-p.x)>0;
}

bool cmf(punct a,punct b)
{
     return fct(a,b)>0;
}

void citire()
{
     freopen ("infasuratoare.in","r",stdin);
     freopen ("infasuratoare.out","w",stdout);

     scanf ("%d",&n);
     scanf ("%lf %lf",&p.x,&p.y);
     sir[0]=p;

     for (int i=1;i<n;i++)
     {
          scanf ("%lf %lf",&sir[i].x,&sir[i].y);

          if (sir[i].y<p.y || (sir[i].y==p.y && sir[i].x<p.x))
          {
               p=sir[i];
               poz=i;
          }
     }
}


int main()
{
     citire();
     punct aux=sir[poz];
     sir[poz]=sir[0];
     sir[0]=aux;
     sort(sir+1,sir+n+1,cmf);
     ind[1]=0;
     ind[2]=1;
     int m=2;
     for (int i=2;i<n;i++)
     {
          while (m>=2 && fct2(sir[ind[m]],sir[i],sir[ind[m-1]])<=0)
               m--;
          ind[++m]=i;
     }

     printf("%d\n",m);
     for (int i=1;i<=m;i++)
          printf("%lf %lf\n",sir[ind[i]].x,sir[ind[i]].y);
     return 0;
}