Cod sursa(job #753873)

Utilizator cahemanCasian Patrascanu caheman Data 30 mai 2012 18:09:16
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define eps 0.000000000001
using namespace std;
struct casy
{
	double x,y;
	void operator = (const casy &other) {
		x=other.x;
		y=other.y;
	}
};
casy p[120001];
casy ll;
int sol[120001];
int nrsol;
bool cmp(casy p1,casy p2)
{
	double ccw,d1,d2;
	ccw=(p1.x-ll.x)*(p2.y-p1.y)-(p1.y-ll.y)*(p2.x-p1.x);
	if(ccw>eps)
		return 1;
	if(fabs(ccw)<eps) {
		d1=(p1.x-ll.x)*(p1.x-ll.x)+(p1.y-ll.y)*(p1.y-ll.y);
		d2=(p2.x-ll.x)*(p2.x-ll.x)+(p2.y-ll.y)*(p2.y-ll.y);
		if(d2-d1>eps)
			return 1;
	}
	return 0;	
}
int main()
{
	freopen("infasuratoarea.in","r",stdin);
	freopen("infasuratoarea.out","w",stdout);
	int n,i,poz;
	casy aux;
	
	double ccw;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	ll.x=p[1].x;
	ll.y=p[1].y;
	poz=i;
	for(i=2;i<=n;i++)
	{
		if(fabs(ll.y-p[i].y)<eps&&ll.x-p[i].x>eps) {
			ll.x=p[i].x;
			ll.y=p[i].y;
			poz=i;
			
		}
		if(ll.y-p[i].y>eps)
		{
			poz=i;
			ll.x=p[i].x;
			ll.y=p[i].y;
		}
	}
	aux=p[poz];
	p[poz]=p[1];
	p[1]=aux;
	sort(p+2,p+n+1,cmp);
	sol[1]=1;
	sol[2]=2;
	nrsol=2;
	p[n+1].x=p[1].x;
	p[n+1].y=p[1].y;
	for(i=3;i<=n+1;i++)
	{
		ccw=(p[sol[nrsol]].x-p[sol[nrsol-1]].x)*(p[i].y-p[sol[nrsol]].y)-(p[sol[nrsol]].y-p[sol[nrsol-1]].y)*(p[i].x-p[sol[nrsol]].x);
		if(ccw>eps)
			sol[++nrsol]=i;
		else
		{
			nrsol--;
			i--;
		}
	}
	printf("%d\n",nrsol-1);
	for(i=1;i<nrsol;i++)
		printf("%lf %lf\n",p[sol[i]].x,p[sol[i]].y);
	return 0;
}