Cod sursa(job #1574926)

Utilizator LegionHagiu Stefan Legion Data 20 ianuarie 2016 22:29:36
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct
{
	double x;
	double y;
	double panta;
};
punct puncte[120001];
punct stiva[120001];
int curent = 2;
int n;
int minx=2000000000, miny = -2000000000,punctales;
bool cmp(punct a,punct b)
{
	if (a.panta < b.panta){ return true; }
	return false;
}
int main()
{
	ifstream in("infasuratoare.in");
	ofstream out("infasuratoare.out");
	int i;
	in >> n;
	for (i = 1; i <= n; i++)
	{
		in >> puncte[i].x;
		in >> puncte[i].y;
		if (puncte[i].x < minx || (puncte[i].x == minx&&puncte[i].y > miny))
		{
			minx = puncte[i].x;
			miny = puncte[i].y;
			punctales = i;
		}
	}
	for (i = 1; i <= n; i++)
	{
		if (i != punctales&&puncte[i].x == puncte[punctales].x)
			puncte[i].panta = -1999999999;
		else if (i != punctales)
			puncte[i].panta = (puncte[punctales].y - puncte[i].y) / (puncte[punctales].x - puncte[i].x);
		else
			puncte[i].panta = -2000000000;
	}
	sort(puncte+1, puncte+n+1, cmp);
	stiva[1] = puncte[1];
	stiva[2] = puncte[2];
	for (i = 3; i <= n; i++)
	{
		if ((puncte[i].y - stiva[curent - 1].y) * (stiva[curent].x - stiva[curent - 1].x)  < (stiva[curent].y - stiva[curent - 1].y) * (puncte[i].x - stiva[curent - 1].x))
		{
			curent--;
			i--;
		}
		else
		{
			curent++;
			stiva[curent] = puncte[i];
		}
	}
	out << curent << "\n";
	for (i = 1; i <= curent; i++)
	{
		out <<setprecision(9) <<fixed<< stiva[i].x << " " << stiva[i].y << "\n";
	}
}