Cod sursa(job #727567)

Utilizator ms-ninjacristescu liviu ms-ninja Data 28 martie 2012 08:59:54
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <algorithm>
#include <cstdio>
using namespace std;
ifstream fin("infasuratoare.in");
#define dim 120005
#define inf 0x3f3f3f3f
#define fs first
#define sc second
pair <double,double>v[dim];
int n,orig=1,ind[dim],vf;
int stiva[dim];

void read()
{
	fin>>n;
	
	for(int i=1;i<=n;++i)
	{
		fin>>v[i].fs >>v[i].sc;
		if(v[i].fs<v[orig].fs || (v[i].fs==v[orig].fs && v[i].sc<v[orig].sc))
			orig=i;
		ind[i]=i;
	}
}
	
inline double panta(int a, int b)
{
	if(v[a].fs==v[b].fs)
		return inf;
	return (v[a].sc-v[b].sc)/(v[a].fs-v[b].fs);
};

struct cmp
{
	bool operator () (const int &a, const int &b)
	{
		return panta(a,orig)<panta(b,orig);
	}
};

inline double det(int a, int b, int c)
{
	return (v[b].fs-v[a].fs)*(v[c].sc-v[a].sc)-(v[c].fs-v[a].fs)*(v[b].sc-v[a].sc);
};

void solve()
{
	sort(ind+1,ind+n+1,cmp());
	
	stiva[++vf]=orig;
	for(int i=1;i<=n;++i)
		if(ind[i]!=orig)
		{
			for(;vf>=2 && det(stiva[vf-1],stiva[vf],ind[i])<0;--vf);
			stiva[++vf]=ind[i];
		}
				
}

void print()
{
	printf("%d\n",vf);
	for(int i=1;i<=vf;++i)
		printf("%lf %lf\n",v[stiva[i]].fs,v[stiva[i]].sc);
}

int main()
{
	freopen ("infasuratoare.out","w",stdout);
	read();
	solve();
	print();
	return 0;
}