Cod sursa(job #2358146)

Utilizator Catalin_BorzaBorza Catalin-Mihai Catalin_Borza Data 27 februarie 2019 21:44:51
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;

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

enum Direction
{
	Left,
	Right
};

struct point
{
	double x, y;
	point() {};
	point(double X, double Y) : x(X), y(Y) {};
	friend istream &operator>> (istream &in, point &p)
	{
		in >> p.x >> p.y;
		return in;
	}
	friend ostream &operator<< (ostream &out, point &p)
	{
		out << fixed << setprecision(6) << p.x << " " << p.y;
		return out;
	}
}P[120001];

int n;

auto slope = [](point a, point b) {return (a.y - b.y) / (a.x - b.x); };
auto turn_direction = [](point a, point b, point c) {return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) > 0 ? Left : Right); };

void swapp(point &a, point &b, double &sa, double &sb)
{
	double aux = sa;
	sa = sb;
	sb = aux;
	point ap = a;
	a = b;
	b = ap;
}

void sort_points()
{
	double slopes[120001];
	for (int i = 1; i < n; i++)
		slopes[i] = slope(P[0], P[i]);
	for (int i = 1; i < n; i++)
		for (int j = i + 1; j < n; j++)
		{
			if (slopes[i] > 0)
			{
				if (slopes[j] > 0 && slopes[i] > slopes[j])
					swapp(P[i], P[j], slopes[i], slopes[j]);
			}
			else
			{
				if (slopes[j] < 0 && slopes[i] > slopes[j] || slopes[j] > 0)
					swapp(P[i], P[j], slopes[i], slopes[j]);
			}
				
		}
}

point s[120001];
int ks = 3;
void Graham()
{
	s[0] = P[0];
	s[1] = P[1];
	s[2] = P[2];
	for (int i = 3; i < n; i++)
	{
		while (turn_direction(s[ks - 2], s[ks - 1], P[i]) == Right)
			ks--;
		s[ks++] = P[i];
	}
}

int main()
{
	f >> n;
	int lpos, dpos;
	double minx = 1000000010, miny = 1000000010;
	for (int i = 0; i < n; i++)
	{
		f >> P[i];
		if (P[i].x < minx)
			minx = P[i].x, lpos = i;
		else if (P[i].x == minx)
			lpos = -1;
		if (P[i].y < miny)
			miny = P[i].y, dpos = i;
		else if (P[i].y == miny)
			dpos = -1;
	}
	lpos = (lpos != -1 ? lpos : dpos);
	if (lpos == -1) return 0;
	point aux = P[0];
	P[0] = P[lpos];
	P[lpos] = aux;
	sort_points();
	Graham();
	g << ks << "\n";
	for (int i = 0; i < ks; i++)
		g << s[i] << "\n";
	return 0;
}