Cod sursa(job #1485711)

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

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

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

	while (true)
	{
		ok = false;
		cosin = 1;
		for (int i = 0; i < v.size(); i++)
		{
			double bc = sqrt(pow((p1 - elemMin.x), 2) + pow(p2 - elemMin.y, 2));
			double ab = sqrt(pow(elemMin.x - v[i].x, 2) + pow(elemMin.y - v[i].y, 2));
			double ac = sqrt(pow(v[i].x - p1, 2) + pow(v[i].y - 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 (k == start)
		{
			break;
		}
		if (ok)
		{
			rez.push_back(v[k]);
			p1 = elemMin.x;
			p2 = elemMin.y;
			elemMin = v[k];
			v.erase(v.begin() + k);
		}
		else
			break;

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

}