Cod sursa(job #1485989)

Utilizator silviu982001Borsan Silviu silviu982001 Data 13 septembrie 2015 15:35:02
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

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

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) - (e3.x * e2.y) - (e2.x * e1.y) - (e3.y * e1.x));
}

int main()
{
    vector<long> rez;
	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);
	rez.push_back(2);
	use[0] = use[1] = use[2] = true;
	for (int i = 3; i < v.size(); i++)
	{
		bool ok = false;
		while (rez.size() > 2)
		{
			if (determ(v[rez[rez.size() - 2]], v[rez[rez.size() - 1]], v[i]) < 0)
			{
				ok = true;
				use[rez[rez.size()-1]] = false;
				rez.pop_back();
			}
			else
			{
				ok = true;
				break;
			}
		}

		if (ok)
		{
			use[i] = true;
			rez.push_back(i);
		}
	}

	for (int i = v.size() - 2; i >= 2; i--)
	{
		if (!use[i])
		{

			bool ok = false;
			while (rez.size() > 2)
			{
				if (determ(v[rez[rez.size() - 2]], v[rez[rez.size() - 1]], v[i]) < 0)
				{
					ok = true;
					use[rez[rez.size() - 1]] = false;
					rez.pop_back();
				}
				else
				{
					ok = true;
					break;
				}
			}

			if (ok)
				rez.push_back(i);
		}
	}

	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;

}