Cod sursa(job #682701)

Utilizator attila3453Geiszt Attila attila3453 Data 19 februarie 2012 13:31:02
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");

const int maxn = 120000;
const int infinit = 1000000000;

float x[maxn], y[maxn];
int init, sol[maxn];
vector<int> ind;

bool sortfunc(int i, int j)
{
	return (x[i] - x[init]) * (y[j] - y[init]) > (x[j] - x[init]) * (y[i] - y[init]);
}

bool right(int i, int j, int k)
{
	return (x[i] * (y[j] - y[k]) + x[j] * (y[k] - y[i]) + x[k] * (y[i] - y[j])) > 0;
}

int main()
{
	int i, n, l = 0, p = 0;

	fi>>n;

	ind.resize(n+1);

	init = 1;

	for(i = 1;i <= n;i++)
	{
		fi>>x[i]>>y[i];
		if(x[i] < x[init] || (x[i] == x[init] && y[i] < y[init]))
			init = i;
        ind[i] = i;
	}

	ind.erase(ind.begin() + init);
	sort(ind.begin(), ind.end(), sortfunc);

	p = 1;
	sol[1] = init;
	for(i = 1;i < n;i++)
	{
		while(p >= 2 && !right(sol[p-1], sol[p], ind[i]))
			p--;
		sol[++p] = ind[i];
	}

	fo<<p<<'\n';
	for(i = 1;i <= p;i++)
		fo<<x[sol[i]]<<' '<<y[sol[i]]<<'\n';

	return 0;
}