Cod sursa(job #339504)

Utilizator razvi9Jurca Razvan razvi9 Data 10 august 2009 09:56:13
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

struct PT
{
	double x,y;
};

PT a[120001];
double X,Y;
int n,i,low,cnt;

double d(PT a,PT b)
{
	return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

bool cmp(PT A,PT B)
{
	X = (A.x - a[1].x) / d(A,a[1]);
	Y = (B.x - a[1].x) / d(B,a[1]);
	return X>Y;
}

bool det(PT a,PT b,PT c)
{
	X = a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
	return X>0;
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	low = 1;
	for(i=1;i<=n;++i)
	{
		scanf("%lf %lf",&X,&Y);
		a[i].x = X;
		a[i].y = Y;
		if(a[i].y < a[low].y || (a[i].y == a[low].y && a[i].x < a[low].x))
			low = i;
	}
	a[0] = a[low];
	a[low] = a[1];
	a[1] = a[0];
	sort(&a[2],&a[n+1],cmp);
	cnt = 2;
	for(i=3;i<=n;++i)
	{
		while(!det(a[cnt-1],a[cnt],a[i]))
			--cnt;
		a[++cnt] = a[i];
	}
	printf("%d\n",cnt);
	for(i=1;i<=cnt;++i)
		printf("%lf %lf\n",a[i].x,a[i].y);
	fclose(stdout);
	return 0;
}