Cod sursa(job #1450400)

Utilizator ccygnusMaygnus Pop ccygnus Data 13 iunie 2015 11:30:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1.e-14;
struct point
{
	double x,y;
};
point p[120005],ll;
int st[120005];
double cp(point p1,point p2,point p3)
{
	return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
int ccw(point p1,point p2,point p3)
{
	double ans=cp(p1,p2,p3);
	if (ans<=-eps)
		return -1;
	if (ans>=eps)
		return 1;
	return 0;
}
double dist(point p1,point p2)
{
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
bool cmp(point a,point b)
{
	int ans=ccw(ll,a,b);
	if (ans==0)
		return dist(ll,a)<dist(ll,b);
	if (ans==1)
		return 1;
	return 0;
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	int i,n,top;
	scanf("%d",&n);
	scanf("%lf%lf",&p[1].x,&p[1].y);
	for(i=2;i<=n;i++)
		{
		scanf("%lf%lf",&p[i].x,&p[i].y);
		if (p[i].y-p[1].y<=-eps)
			swap(p[1],p[i]);
		else
			if (fabs(p[i].y-p[1].y)<eps)
				if (p[i].x-p[1].x<=-eps)
					swap(p[1],p[i]);
		}
	ll=p[1];
	sort(p+2,p+n+1,cmp);
	p[n+1]=ll;
	st[1]=1;
	st[2]=2;
	top=2;
	i=3;
	while(i<=n+1)
	  {
	  if (ccw(p[st[top-1]],p[st[top]],p[i])>0)
		  st[++top]=i,i++;
	  else
		  top--;
   	  }
	printf("%d\n",top-1);
	for(i=1;i<top;i++)
		printf("%lf %lf\n",p[st[i]].x,p[st[i]].y);
return 0;
}