Cod sursa(job #1486021)

Utilizator silviu982001Borsan Silviu silviu982001 Data 13 septembrie 2015 16:39:39
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#define val 10e-12
using namespace std;

struct elem
{
	double x, y;
};
vector<elem> v;
vector<long> rez;

int value_sort(const void* a, const void* b)
{
	elem* pa = *(elem**)a;
	elem* pb = *(elem**)b;

	if (pb->y < pa->y)
		return 1;
	else if (pa->y < pb->y)
		return -1;
	return 0;
}

static bool MyDataSorter(const elem& lhs, const elem& rhs)
{
	if (lhs.y < rhs.y)
		return true;
	else
	if (lhs.y == rhs.y && lhs.x > rhs.x)
		return true;
	return false;
}

double determ(elem e1, elem e2, elem e3)
{
	return ((e1.x*e2.y) + (e2.x*e3.y) + (e3.x*e1.y) - (e1.y*e2.x) - (e2.y*e3.x) - (e3.y*e1.x));
}

int main()
{
	
	bool *use;
	ifstream input("infasuratoare.in");
	int n;
	input >> n;
	use = new bool[n];
	elem *e;
	for (int i = 0; i < n; i++)
	{
		e = new elem();
		input >> e->x;
		input >> e->y;
		v.push_back(*e);
		use[i] = false;
	}
	input.close();

	sort(v.begin(), v.end(), MyDataSorter);

	rez.push_back(0);
	rez.push_back(1);
	use[0] = use[1] = true;
	for (int i = 2; i < v.size(); i++)
	{
		while (!use[i] && determ(v[rez[rez.size() - 2]], v[rez[rez.size() - 1]], v[i]) < val)
		{
			use[rez[rez.size() - 1]] = false;
			rez.pop_back();
			if (rez.size() < 2)
				break;
		}
		use[i] = true;
		rez.push_back(i);
	}

	for (int i = v.size(); i >= 0; i--)
	{

		while ((i == 1 || !use[i]) && determ(v[rez[rez.size() - 2]], v[rez[rez.size() - 1]], v[i]) < val)
		{
			use[rez[rez.size() - 1]] = false;
			rez.pop_back();
			if (rez.size() < 2)
				break;
		}
		if (!use[i])
		{
			rez.push_back(i);
			use[i] = true;
		}



	}

	ofstream output("infasuratoare.out");
	output << rez.size() << endl;
	for (int i = 0; i < rez.size(); i++)
		output << setprecision(9) << fixed << v[rez[i]].x << " " << v[rez[i]].y << endl;
	output.close();
	return 0;

}