Cod sursa(job #1485672)

Utilizator silviu982001Borsan Silviu silviu982001 Data 12 septembrie 2015 17:39:42
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <list>
#include <iomanip>
#include <cmath>
#include <cstdio>
using namespace std;

struct elem
{
	double x, y;
};

int main()
{
	list <elem> rez;
	bool *use;
	ifstream input("infasuratoare.in");
	int n;
	input >> n;
	double **a = (double **)new double[n];
	use = new bool[n];
	for (int i = 0; i < n; i++)
	{
		a[i] = (double*)new double[2];
		input >> a[i][0];
		input >> a[i][1];
		use[i] = false;
	}
	input.close();
	int min = 0, start = 0, k = 0;
	for (int i = 1; i < n; i++)
	if (a[i][1] < a[min][1])
		min = i;
	else if (a[i][1] == a[min][1] && a[i][0] < a[min][0])
		min = i;
	start = min;
	use[start] = true;
	elem *e = new elem();
	e->x = a[min][0];
	e->y = a[min][1];
	rez.push_back(*e);
	double p1 = a[min][0] - 10, p2 = a[min][1];
	double cosin = 1;
	bool ok = true;

	while (true)
	{
		ok = false;
		cosin = 1;
		for (int i = 0; i < n; i++)
		{
			double bc = sqrt(pow((p1 - a[min][0]), 2) + pow(p2 - a[min][1], 2));
			double ab = sqrt(pow(a[min][0] - a[i][0], 2) + pow(a[min][1] - a[i][1], 2));
			double ac = sqrt(pow(a[i][0] - p1, 2) + pow(a[i][1] - p2, 2));
			double cos = (pow(ab, 2) + pow(bc, 2) - pow(ac, 2)) / (2 * ab * bc);
			if (cosin > cos)
			{
				cosin = cos;
				k = i;
				ok = true;
			}
		}
		if (use[k])
		{
			break;
		}
		if (ok)
		{
			e = new elem();
			e->x = a[k][0];
			e->y = a[k][1];
			rez.push_back(*e);
			use[k] = true;
			p1 = a[min][0];
			p2 = a[min][1];
			min = k;
		}
		else
			break;

	}
	ofstream output("infasuratoare.out");
	output << rez.size() <<endl;
	for (list<elem>::iterator it = rez.begin(); it != rez.end(); ++it)
		output << it->x << " " << it->y << endl;
	output.close();
	return 0;

}