Cod sursa(job #2454872)

Utilizator silviu982001Borsan Silviu silviu982001 Data 10 septembrie 2019 01:42:21
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

struct Point
{
	double x, y;
};

int n;
vector<Point> v, sol;

bool operator<(const Point& p1, const Point& p2)
{
	if (p1.y == p2.y)
		return p1.x > p2.x;

	return p1.y > p2.y;
}

long double determinant(const Point& p1, const Point& p2, const Point& p3)
{
	return p1.x * p2.y + p2.x * p3.y + p1.y * p3.x - p2.y * p3.x - p1.x * p3.y - p1.y * p2.x;
}

bool cmp(const Point& p1, const Point& p2)
{
	return determinant(v[0], p1, p2) > 0;
}

int main()
{
	ifstream fin("infasuratoare.in");
	fin >> n;

	for (int i = 0; i < n; ++i)
	{
		Point p;
		fin >> p.x >> p.y;
		v.push_back(p);
	}

	for (int i = 1; i < n; ++i)
		if (v[0] < v[i])
			swap(v[0], v[1]);

	sort(v.begin()+1, v.end(), cmp);

	sol.push_back(v[0]);

	for (int i = 1; i < n; ++i)
	{
		while (sol.size() > 1 && determinant(sol[sol.size() - 2], sol[sol.size() - 1], v[i]) < 0)
			sol.pop_back();

		sol.push_back(v[i]);
	}

	ofstream fout("infasuratoare.out");
	fout << sol.size() << '\n';
	for (Point p : sol)
		fout << setprecision(9) << fixed << p.x << ' ' << p.y << '\n';
	fout.close();

	return 0;
}