Cod sursa(job #429785)

Utilizator slayer4uVictor Popescu slayer4u Data 30 martie 2010 14:19:50
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

#define NMAX 10000

vector <pair <double, double> > puncte;
vector <pair <int, double> > pante;

long st[NMAX], n;
double a, b;

int cmpf(pair <double, double> a, pair <double, double> b)
{
	if (a.first < b.first)
		return 1;
	else
	if (a.first == b.first)
		return a.second < b.second;
	return 0;
}


int cmpf2(pair <int, double> a, pair <int, double> b)
{
	return a.second < b.second;
}

double panta(long i, long j)
{
	return (double)(puncte[j].second - puncte[i].second) / (puncte[j].first - puncte[i].first);
}

double semn(long i, long j, long k)
{
	return (double)puncte[i].first * puncte[j].second + puncte[j].first * puncte[k].second + puncte[k].first * puncte[i].second - puncte[i].second * puncte[j].first - puncte[j].second * puncte[k].first - puncte[k].second * puncte[i].first;
}

int main()
{
	freopen ("infasuratoare.in", "rt", stdin);
	freopen ("infasuratoare.out", "wt", stdout);

	scanf("%ld", &n);
	for (long i = 0; i < n; ++i)
	{
		scanf("%lf %lf", &a, &b);
		puncte.push_back(make_pair(a, b));
	}

	sort(puncte.begin(), puncte.end(), cmpf);
	
	for (long i = 1; i < n; ++i)
		pante.push_back(make_pair(i, panta(0, i)));

	sort(pante.begin(), pante.end(), cmpf2);

	st[0] = 2;
	st[1] = 0;
	st[2] = pante[0].first;
	for (long i = 1; i < n - 1; ++i)
	{
		while (semn(st[st[0] - 1], st[st[0]], pante[i].first) < 0)
			--st[0];
		st[++st[0]] = pante[i].first;
	}

	printf("%ld\n", st[0]);
	for (long i = 1; i <= st[0]; ++i)
		printf("%lf %lf\n", puncte[st[i]].first, puncte[st[i]].second);

	return 0;
}