Cod sursa(job #1184694)

Utilizator stef93Stefan Gilca stef93 Data 13 mai 2014 20:36:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <climits>
#include <cfloat>
#include <algorithm>

using namespace std;

struct punct
{
	double x, y;
};

punct puncte[120003];
punct stiva[120003];

double cp(punct &a, punct &b , punct &c)
{
	return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}

bool cmp(punct a, punct b)
{
	if (cp(puncte[0], a, b) < 0)
	{
		return true;
	}
	return false;
}


int main()
{
	ifstream in("infasuratoare.in");
	ofstream out("infasuratoare.out");

	int n , i , poz;
	punct extremaStanga;
	extremaStanga.x = DBL_MAX;
	extremaStanga.y = DBL_MAX;

	in >> n;

	for (i = 0; i < n; i++)
	{
		in >> puncte[i].x >> puncte[i].y;
		if (puncte[i].x < extremaStanga.x)
		{
			extremaStanga.x = puncte[i].x;
			extremaStanga.y = puncte[i].y;
			poz = i;
		}
		else
		{
			if (puncte[i].x == extremaStanga.x)
			{
				if (puncte[i].y < extremaStanga.y)
				{
					extremaStanga.x = puncte[i].x;
					extremaStanga.y = puncte[i].y;
				}
			}
		}
	}

	swap(puncte[0], puncte[poz]);

	sort(puncte + 1, puncte + n, cmp);

	stiva[0] = puncte[0];
	stiva[1] = puncte[1];
	poz = 1;

	for (i = 2; i < n; i++)
	{
		while (poz >= 1 && cp(stiva[poz - 1], stiva[poz], puncte[i]) > 0)
			poz--;
		stiva[++poz] = puncte[i];
	}

	out.setf(ios::floatfield, ios::fixed);
	out.precision(9);

	out << poz + 1 << '\n';
	for (i = poz; i >= 0; i--)
	{
		out << stiva[i].x << ' ' << stiva[i].y << '\n';
	}
	return 0;
}