Cod sursa(job #303121)

Utilizator rethosPaicu Alexandru rethos Data 9 aprilie 2009 16:08:31
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <stdio.h>
#include <algorithm>
#define NM 120001
using namespace std;
struct pct{float x,y;} a[NM],minim,st[NM];
int vf;
int n;
int cmp(pct a,pct b)
{if (b.x==minim.x&&b.y==minim.y) return 1;
 if (b.x==minim.x) return 1;
 if ((a.y-minim.y)*(b.x-minim.x)<(a.x-minim.x)*(b.y-minim.y)) return 1;
 return 0;
}
float det(pct a,pct b,pct c)
{return (a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-c.y*a.x);
}
int main()
{freopen("infasuratoare.in","r",stdin);
 freopen("infasuratoare.out","w",stdout);
 scanf("%d",&n);
 int i;
 for (i=1;i<=n;i++)
	 {scanf("%f %f",&a[i].x,&a[i].y);
	  if (minim.x>a[i].x||(minim.x==a[i].x&&minim.y>a[i].y)||i==1)
			 {minim=a[i];
			 }
     }		 
 sort(a+1,a+n+1,cmp);
 st[++vf]=minim;
 for (i=1;i<n;i++)
	 {while (vf>1&&det(st[vf-1],st[vf],a[i])<=0)
		  {vf--;
		  }
	  st[++vf]=a[i];
	 }
 printf("%d\n",vf);	 
 for (i=1;i<=vf;i++)
	 {printf("%f %f\n",st[i].x,st[i].y);
	 }
 return 0;
}