Cod sursa(job #729419)

Utilizator geniucosOncescu Costin geniucos Data 29 martie 2012 16:18:58
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int N,i,p,m,vect[100];
struct nod
{
	double x,y;
	double unghi;
};
nod a[15002],aux;
double x,y,ip,l1,l2,min1;
bool cmp1(nod a,nod b)
{
	if (a.unghi>b.unghi) return 1;
	else return 0;
}

bool intoarcere(int x,int y,int z)
{
	double a1,b1,c1,s;
	a1=a[x].y-a[y].y;
	b1=a[y].x-a[x].x;
	c1=a[x].x*a[y].y-a[y].x*a[x].y;
	s=a1*a[z].x+b1*a[z].y+c1;
	if (s<=0) return 1;
	else return 0;
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
		scanf("%lf%lf",&a[i].x,&a[i].y);
	min1=10000;
	for (i=1;i<=N;i++)
		if (a[i].y<min1)
		{
			min1=a[i].y;
			p=i;
		}
		else
			if (a[i].y==min1&&a[i].x<a[p].x)
				p=i;
	aux=a[1];
	a[1]=a[p];
	a[p]=aux;
	for (i=2;i<=N;i++)
	{
		l1=1.0*(a[i].y-a[1].y);
		l2=1.0*(a[i].x-a[1].x);
		ip=sqrt(l1*l1+l2*l2);
		a[i].unghi=l2/ip;
	}
	sort(a+2,a+N+1,cmp1);
	m=3;
	vect[1]=1;
	vect[2]=2;
	vect[3]=3;
	for (i=4;i<=N;i++)
	{
		while (intoarcere(vect[m-1],vect[m],i)&&m>2) 
			m--;
		m++;
		vect[m]=i;
	}
	printf("%d\n",m);
	for (i=1;i<=m;i++)
		printf("%.6lf %.6lf\n",a[vect[i]].x,a[vect[i]].y);
	return 0;
}