Cod sursa(job #681802)

Utilizator attila3453Geiszt Attila attila3453 Data 17 februarie 2012 20:15:10
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

struct punct
{
	float x, y;
	punct () { x = y = 0; }
	punct(float X, float Y) { x = X; y = Y; }
};

vector<punct> puncte;
punct init(0,0);

bool sortfunc(punct a, punct b)
{	
	return (a.x - init.x) * (b.y - init.y) < (b.x - init.x) * (a.y - init.y);
}

bool right(punct a, punct b, punct c)
{
	return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) > 0;
}

int main()
{
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);

	int i, n, j = 0;
	float x, y;

	scanf("%d",&n);

	for(i = 0;i < n;i++)
	{
		scanf("%f %f", &x, &y);
		puncte.push_back(punct(x, y));
		if(x < puncte[j].x or (x == puncte[j].x and y < puncte[j].y))
			j = i;
	}

	vector<punct> sol;

    init = puncte[j];
	puncte.erase(puncte.begin() + j);
	sort(puncte.begin(), puncte.end(), sortfunc);

	sol.push_back(init);

	for(i = 0;i < puncte.size();i++)
	{
		while(sol.size() > 1 and right(*(sol.end() - 2), *(sol.end() - 1), puncte[i]))
			sol.pop_back();

		sol.push_back(puncte[i]);
	}

	printf("%d\n", sol.size());

	for(i = sol.size() - 1;i >= 0;i--)
		printf("%.7f %.7f\n", sol[i].x, sol[i].y);

	return 0;
}