Cod sursa(job #650174)

Utilizator ELHoriaHoria Cretescu ELHoria Data 17 decembrie 2011 15:06:36
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;
	};
};

int semn(PDD a, PDD b, PDD c)
{
    double A = a.nd-b.nd, B = b.st-a.st, C = a.st*b.nd - b.st*a.nd;
    return cmp(A * c.st + B * c.nd + C, 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 &&  semn(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;
}