Cod sursa(job #650175)

Utilizator ELHoriaHoria Cretescu ELHoria Data 17 decembrie 2011 15:07:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <algorithm>
#include <bitset>
#include <iomanip>
#define PDD pair<double,double>
#define st first
#define nd second
#define EPS 1e-12

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int N , H , s[12005];
PDD v[120005] , P[120005];
bitset<120005> use;

inline int cmp(const double a,const double b)
{
	if(a + EPS < b) return -1;
	if(b + EPS < a) return 1;
	return 0;
}

struct PDD_cmp{ bool operator() (const PDD &x,const PDD &y)
	const { int r = cmp(x.st,y.st);
	if(r!=0) return r == -1;
	return cmp(x.nd,y.nd) == -1;
	};
};

static int ccw(const PDD &a,const PDD &b,const PDD &c)
{
	double area2 = (b.st-a.st)*(c.nd-a.nd) - (b.nd-a.nd)*(c.st-a.st);
	return cmp(area2,0);
}

void convex_hull()
{
	int i = 3, pas = 1 , k = 0 ;
	sort(v + 1,v + N + 1,PDD_cmp());

	use[2] = true;
	s[++k] = 1 , s[++k] = 2;
	while(use[1] == false)
	{
		while(use[i])
		{
			if(i == N) pas = -1;
			i+=pas;
		}
		while(k>=2 &&  ccw(v[s[k-1]],v[s[k]],v[i]) ==  -1) 
			use[s[k--]] = 0;
		s[++k] = i ,  use[i] = true;
	}
	H = k - 1;
	for(i = 1;i<=H;++i)
		P[i] = v[s[i]];
}

int main()
{
	fin>>N;
	for(int i = 1;i<=N;++i)
		fin>>v[i].st>>v[i].nd;

	convex_hull();
	fout<<H<<'\n';
	for(int i = 1;i<=H;++i)
		fout<<fixed<<setprecision(6)<<P[i].st<<' '<<P[i].nd<<'\n';
	return 0;
}