Cod sursa(job #753677)

Utilizator SmarandaMaria Pandele Smaranda Data 30 mai 2012 11:56:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define eps 1.e-12
using namespace std;

struct POINT 
{
	double x,y;
};
POINT m[120012];
POINT ll;
long hull[120012];
long ccw(POINT a , POINT b , POINT c)
{
	double ca=(b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
	if (fabs(ca)<eps)
		return 0;
	if (ca>=eps)
		return 1;
	return -1;
}
double dist (POINT a  , POINT b)
{
	return sqrt(   (a.x-b.x)*(a.x-b.x) +  (a.y-b.y)*(a.y-b.y)  );
}

long samepoint (POINT a  ,POINT b)
{
	if (fabs(a.x-b.x)<eps && fabs(a.y-b.y)<eps)
		return 1;
	return 0;
}

long comp(POINT a , POINT b, POINT c)
{
	double ca,d1,d2;
	if (samepoint(a,b)==1)
		return 0;
	ca=ccw(a,b,c);
	/*if (ca==1)
		return 1;*/
	if (ca==0)
	{
		d1=dist(a,b);
		d2=dist(a,c);
		if (d1-d2<=-eps)
			return 1;
		else
			return 0;
	}
	if (ca==-1)
		return 0;
	else
		return 1;
	//return 0;
}

long part(long st, long dr)
{
	long i,j,med;
	POINT p;
	POINT aux;
	i=st-1;
	med=(st+dr)/2;
	p=m[med];
	j=dr+1;
	while (1)
	{
		do {++i;}while (!samepoint(p,m[i]) && comp(ll,m[i],p));
		do {--j;}while (!samepoint(p,m[j]) && comp(ll,p,m[j]));
		if (i<j)
		{
			aux=m[i];
			m[i]=m[j];
			m[j]=aux;
		}
		else
			return j;
	}
}

void quick(long st  , long dr)
{
	long sp;
	if (st<dr)
	{
		sp=part(st,dr);
		quick(st,sp);
		quick(sp+1,dr);
	}
}

struct cmp {
	bool operator () (const POINT &A , const POINT &B) {
		double ca,d1,d2;
		/*if (samepoint(ll,A)==1)
			return 0;*/
		ca=ccw(ll,A,B);
		/*if (ca==1)
			return 1;*/
		if (ca==0)
		{
			d1=dist(ll,A);
			d2=dist(ll,B);
			if (d1-d2<=-eps)
				return 1;
			else
				return 0;
		}
		if (ca==-1)
			return 0;
		else
			return 1;
	}
};

int main()
{
	long n,i,p=0,c;
	POINT aux;
	
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	
	scanf("%ld",&n);
	scanf("%lf%lf",&m[1].x,&m[1].y);
	for (i=2;i<=n;i++)
		{
			scanf("%lf%lf",&m[i].x,&m[i].y);
			if ((m[1].y-m[i].y)>=eps || (fabs(m[1].y-m[i].y)<eps && (m[1].x-m[i].x)>=eps))
			{
				aux=m[1];
				m[1]=m[i];
				m[i]=aux;
			}
		}
	ll=m[1];
	//quick(2,n);
	sort(m+2,m+1+n,cmp());
	m[n+1]=m[1];
	hull[1]=1;
	hull[2]=2;
	p=2;
	i=3;
	while (i<=n+1)
	{
		c=ccw(m[hull[p-1]],m[hull[p]],m[i]);
		if (c>0)
		{
			hull[++p]=i;
			i++;
		}
		else
		{
			p--;
		}
	}
	printf("%ld\n",p-1);
	for (i=1;i<p;i++)
		printf("%.6lf %.6lf\n",m[hull[i]].x,m[hull[i]].y);
	return 0;
}