Cod sursa(job #2400659)

Utilizator florin_salamFlorin Salam florin_salam Data 8 aprilie 2019 23:20:07
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <iomanip>
#include <fstream>
#include <algorithm>

#define pdd pair <double, double>
#define mp make_pair

using namespace std;

const int NMAX = 120005;

class point
{
public:
	pdd coord, slope;
	point()
	{
		coord = slope = mp(0.0, 0.0);
	}
	point(pdd a, pdd b)
	{
		coord = a;
		slope = b;
	}
	inline bool operator<(const point &other) const
	{
		return this->slope.first * other.slope.second < this->slope.second * other.slope.first;
	}
};

int n;
pdd points[NMAX], st[NMAX];
point a[NMAX];

pdd GetSlope(pdd a, pdd b)
{
	pdd slope = mp((b.second - a.second), (b.first - a.first));
	if ((slope.second < 0 && slope.first < 0) || (slope.second < 0 && slope.first > 0))
	{
		slope.first *= -1;
		slope.second *= -1;
	}
	return slope;
}

bool PositiveDet(pdd a, pdd b, pdd c)
{
	return (((a.first * b.second + b.first * c.second + c.first * a.second) - (b.second * c.first + c.second * a.first + a.second * b.first)) > 0);
}

int main()
{
	ifstream fin("infasuratoare.in");
	ofstream fout("infasuratoare.out");
	fin >> n;
	pdd start = mp(1e9 + 5, 1e9 + 5);
	int startPos;
	for (int i = 1;i <= n;++i)
	{
		fin >> points[i].first >> points[i].second;
		if (points[i].first < start.first)
		{
			start = points[i];
			startPos = i;
		}
		else if (points[i].first == start.first && points[i].second < start.second)
		{
			start = points[i];
			startPos = i;
		}
	}
	int m = 0;
	for (int i = 1;i <= n;++i)
	{
		if (i == startPos)
			continue;
		a[++m] = point(points[i], GetSlope(start, points[i]));
	}
	sort(a + 1, a + m + 1);
	int top = 0;
	st[++top] = start;
	st[++top] = a[1].coord;
	for (int i = 2;i <= m;++i)
	{
		while (top > 2 && !PositiveDet(st[top - 1], st[top], a[i].coord))
			--top;
		st[++top] = a[i].coord;
	}
	fout << top << "\n";
	fout << setprecision(12) << fixed;
	for (int i = 1;i <= top;++i)
		fout << st[i].first << " " << st[i].second << "\n";
	fin.close();
	fout.close();
	return 0;
}