Cod sursa(job #560652)

Utilizator mraresMardare Rares mrares Data 18 martie 2011 17:02:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define nmax 120005
#define maxx 100000
using namespace std;

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

int n;
int init;
double x[nmax], y[nmax];
int v[nmax];
int s[nmax];

bool cmp(int i, int j)
{
	return (double) (x[i] - x[init]) * (y[j] - y[init]) < (double) (x[j] - x[init]) * (y[i] - y[init]);
}

long double det(int i1, int i2, int i3)
{
	return (long double) x[i1] * y[i2] + x[i2] * y[i3] + x[i3] * y[i1] - y[i1] * x[i2] - y[i2] * x[i3] - y[i3] * x[i1];
	// > la dreapta
	// < stanga
}

int main()
{
	int i;
	fin >> n;
	init = 0;
	x[init] = y[init] = maxx;
	for(i = 1; i <= n; ++ i)
	{
		fin >> x[i] >> y[i];
		if(x[i] < x[init] || (x[i] == x[init]  && y[i] < y[init]))
			init = i;
	}
	for(i = 1; i <= n; ++ i)
	{
		if(i == init) continue;
		v[++v[0]] = i;
	}
	sort(v + 1, v + v[0] + 1, cmp);
	s[0] = 1;
	s[s[0]] = init;
	for(i = 1; i <= v[0]; ++ i)
	{
		if(init == v[i]) continue;
		while(det(s[s[0] - 1], s[s[0]], v[i]) > 0 && s[0] >= 2) --s[0];
		s[++s[0]] = v[i];
	}
	s[++s[0]] = init;
	fout << fixed << setprecision(6);
	fout << s[0] - 1 << "\n";
	reverse(s + 1, s + s[0] + 1);
	for(i = 1; i < s[0]; ++i)
		fout << x[s[i]] << " " << y[s[i]] << "\n";
	return 0;
}