Cod sursa(job #583965)

Utilizator cdascaluDascalu Cristian cdascalu Data 23 aprilie 2011 14:11:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<stdio.h>
#include<algorithm>
#define Nmax 120001
#define INF 1000000010
using namespace std;
int N,minP,st[Nmax];
struct pct
{
	double x,y;
}v[Nmax],p,var;
void read()
{
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&N);
	int i;
	p.x = p.y = INF;
	for(i=1;i<=N;++i)
	{
		scanf("%lf%lf",&v[i].x,&v[i].y);
		if(v[i].x<p.x || v[i].x==p.x && v[i].y<p.y)
		{
			p = v[i];
			minP = i;
		}
	}
}
int cmpf(pct a,pct b)
{
	return ( (a.x-p.x)*(b.y-p.y) ) > ( (a.y-p.y)*(b.x-p.x) );
}
double det(double x1,double y1,double z1,double x2,double y2,double z2,double x3,double y3,double z3)
{
	return (x1*y2*z3 + x2*y3*z1 + x3*y1*z2 - z1*y2*x3 - z2*y3*x1 - z3*y1*x2);
}
int main()
{
	read();
	int i;
	
	var = v[minP];
	v[minP] = v[1];
	v[1] = var;
	sort(v+2,v+N+1,cmpf);
	st[1] = 1;
	st[2] = 2;
	int lev = 2;
	for(i=3;i<=N;++i)
	{
		while(lev>=2 && det(v[st[lev-1]].x, v[st[lev-1]].y, 1.0f, v[st[lev]].x, v[st[lev]].y, 1.0f,v[i].x, v[i].y, 1.0f) < 0)
			--lev;
		st[++lev] = i;
	}
	printf("%d\n",lev);
	for(i=1;i<=lev;++i)
		printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
	return 0;
}