Cod sursa(job #2545750)

Utilizator Catalin_BorzaBorza Catalin-Mihai Catalin_Borza Data 13 februarie 2020 15:07:19
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

struct point
{
	double x, y;
	friend istream& operator>>(istream& in, point& p)
	{
		p = point();
		in >> p.x >> p.y;
		return in;
	}
	friend ostream& operator<<(ostream& out, point& p)
	{
		out << p.x << " " << p.y;
		return out;
	}
};

vector<point> V = vector<point>();
int n;

double slope(point p1, point p2)
{
	return (p1.y - p2.y) / (p1.x - p2.x);
}

double ccw(point p1, point p2, point p3)
{
	return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

vector<point> Graham(vector<point> input, point left)
{
	vector<point> result = vector<point>();
	result.push_back(left);
	result.push_back(input[0]);
	input.erase(input.begin());
	for (auto it : input)
	{
		while (result.size() > 1 && ccw(result[result.size() - 2], result.back(), it) < 0)
			result.pop_back();
		result.push_back(it);
	}
	return result;
}

int main()
{
	in >> n;
	point p;
	for (int i = 0; i < n; i++)
	{
		in >> p;
		V.push_back(p);
	}
	point chosen_left = V[0];

	int i = 0, pos = 0;
	for (auto it : V)
	{
		if (it.x < chosen_left.x || it.x == chosen_left.x && it.y < chosen_left.y)
		{
			chosen_left = it;
			pos = i;
		}
		i++;
	}
	V.erase(V.begin() + pos);
	sort(V.begin(), V.end(), [chosen_left](point p1, point p2) {return slope(p1, chosen_left) < slope(p2, chosen_left); });

	auto result = Graham(V, chosen_left);
	out << result.size() << "\n";
	for (auto it : result)
		out << setprecision(13) << it << "\n";

	return 0;
}