Cod sursa(job #302240)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 8 aprilie 2009 19:23:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <algorithm>
#define INf 1000000001
using namespace std;
struct point{double x,y;}P,aux,a[120005],Q[120005];


inline double isLeft(point P1, point P2,point P){
	 return (P2.x-P1.x)*(P.y-P1.y)- (P.x-P1.x)*(P2.y-P1.y);
}

int comp(point x,point y){
  return (isLeft(x,y,P)>0);
}

int main(){
  freopen ("infasuratoare.in","r",stdin);
  freopen ("infasuratoare.out","w",stdout);
  int i,j,k,l,m,n,LD,q;

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

  P.x=INf; P.y=INf;
  for (i=1;i<=n;++i)
    if (a[i].x < P.x || (a[i].x==P.x && a[i].y<P.y)){
      P.x=a[i].x; P.y=a[i].y; LD=i;
    }
  aux=a[LD]; a[LD]=a[n]; a[n]=aux;
  sort(a+1,a+n,comp);

  Q[1]=P;
  Q[2]=a[1];
  q=2;
  for (i=2;i<=n;++i){
    while ( isLeft(Q[q-1],a[i],Q[q]) > 0)q--;
    Q[++q]=a[i];
  }

  printf("%d\n",q-1);
  for (i=2;i<=q;++i)
    printf("%lf %lf\n",Q[i].x,Q[i].y);
return 0;
}