Cod sursa(job #682707)

Utilizator attila3453Geiszt Attila attila3453 Data 19 februarie 2012 13:44:50
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, sol;
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 right(punct a, punct b, punct c)
{
    return (a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - c.x * b.y - a.x * c.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);

	puncte.resize(n);

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

    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 = 0;i < (signed)sol.size();i++)
		printf("%f %f\n", sol[i].x, sol[i].y);

	return 0;
}