Cod sursa(job #2308946)

Utilizator florin_salamFlorin Salam florin_salam Data 28 decembrie 2018 02:33:46
Problema Infasuratoare convexa Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

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

using namespace std;

const int NMAX = 120005;

struct el
{
	double dy, dx, x, y;
	el()
	{
		this->dy = this->dx = this->x = this->y = 0;
	}
	el(const double &dy, const double &dx, const double &x, const double &y)
	{
		this->dy = dy;
		this->dx = dx;
		this->x = x;
		this->y = y;
	}
	inline bool operator<(const el &other) const
	{
		return this->dy * other.dx < other.dy * this->dx;
	}
};

el a[NMAX];
pdd v[NMAX], st[NMAX];
int n, m, top;

inline pdd Slope(const double &x1, const double &y1, const double &x2, const double &y2)
{
	double retdy = y2 - y1, retdx = x2 - x1;

	if ((retdy < 0 && retdx < 0) || (retdy > 0 && retdx < 0))
		retdy = -retdy, retdx = -retdx;
	return mp(retdy, retdx);
}

inline 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;
	double startx = 1e9 + 1, starty = 1e9 + 1;
	int p;
	for (int i = 1;i <= n;++i)
	{
		fin >> v[i].first >> v[i].second;
		if (startx > v[i].first)
		{
			startx = v[i].first;
			starty = v[i].second;
			p = i;
		}
		else if (startx == v[i].first && starty > v[i].second)
		{
			starty = v[i].second;
			p = i;
		}
	}
	int cnt = 0;
	for (int i = 1;i <= n;++i)
	{
		if (i != p)
		{
			pdd aux = Slope(startx, starty, v[i].first, v[i].second);
			if (aux.second == 0)
				a[n - (++cnt)] = el(aux.first, aux.second, v[i].first, v[i].second);
			else
				a[++m] = el(aux.first, aux.second, v[i].first, v[i].second);
		}
	}
	m += cnt;
	sort(a + 1, a + m + 1);
	st[++top] = mp(startx, starty);
	st[++top] = mp(a[1].x, a[1].y);
	for (int i = 2;i <= m;++i)
	{
		pdd curr = mp(a[i].x, a[i].y);
		while (top > 2 && !PositiveDet(st[top - 1], st[top], curr))
			--top;
		st[++top] = curr;
	}
	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;
}