Cod sursa(job #681840)

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

using namespace std;

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

vector<punct> puncte;
punct init;

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

bool conv(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 < n - 1;i++)
	{
		while(sol.size() > 1 and conv(*(sol.end() - 2), *(sol.end() - 1), puncte[i]))
			sol.pop_back();

		sol.push_back(puncte[i]);
	}

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

	for(i = 0;i < sol.size();i++)
		printf("%.6f %.6f\n", sol[i].x, sol[i].y);

	return 0;
}