Cod sursa(job #703857)

Utilizator iuli1505Parasca Iuliana iuli1505 Data 2 martie 2012 14:59:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<cstdio>
#include<utility>
#include<algorithm>
#define nmax 120002
#define X first
#define Y second
#define det(A,B,C) A.X*B.Y+B.X*C.Y+C.X*A.Y-B.Y*C.X-A.X*C.Y-B.X*A.Y
#define lg(A,B) (A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y)
#define punct pair<double, double>
using namespace std;
int n,v,poz,q;
double zero=0.00000001,x,y;
punct p[nmax],P,Q[nmax];
int fct(punct A, punct B, punct C)
{
	double delta=det(A,B,C),AB,AC;
	if(delta>zero)
		return 1;
	if(delta<-zero)
		return 0;
	AB=lg(A,B);
	AC=lg(A,C);
	if((AC-AB)>delta)
		return 1;
	return 0;
}
int crit(punct A, punct B)
{
	return fct(p[0],A,B);
}
void infasuratoare()
{
	int i;
	Q[0]=p[0];
	Q[1]=p[1];
	q=1;
	for(i=2;i<n;i++)
	{
		while(!fct(Q[q-1],Q[q],p[i]))
			q--;
		q++;
		Q[q]=p[i];
	}
}
int main()
{
	int i;
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d", &n);
	scanf("%lf%lf", &x, &y);
	p[0]=make_pair(x,y);
	P=p[0];
	poz=0;
	for(i=1;i<n;i++)
	{
		scanf("%lf%lf", &x, &y);
		p[i]=make_pair(x,y);
		if(p[i]<P)
		{
			P=p[i];
			poz=i;
		}
	}
	P=p[poz];
	p[poz]=p[0];
	p[0]=P;
	sort(p+1,p+n,crit);
	infasuratoare();
	printf("%d\n", q+1);
	for(i=0;i<=q;i++)
		printf("%.6lf %.6lf\n", Q[i].X, Q[i].Y);
	return 0;
}