Cod sursa(job #2294518)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 2 decembrie 2018 15:19:30
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

#define NMAX 120005
#define input "infasuratoare.in"
#define output "infasuratoare.out"

using namespace std;

ifstream in(input);
ofstream out(output);

struct p
{
	long double x, y;
} points[NMAX], stack[NMAX];
p lowest = { 1000000005, 1000000005 };
int points_size, lowest_size, stack_size;

void Swap(p &A, p &B)
{
	p aux = A;
	A = B;
	B = aux;
}

void Read_Data()
{
	in >> points_size;
	for (int i = 1; i <= points_size; i++)
	{
		in >> points[i].x >> points[i].y;
		if (points[i].x < lowest.x)
			lowest = points[i], lowest_size = i;
		else if (points[i].x == lowest.x)
		{
			if (points[i].y < lowest.y)
				lowest = points[i], lowest_size = i;
		}
	}
	Swap(points[1], points[lowest_size]);
}

double Tan_of_Angle(p A, p B, p C)
{
	return (double)(B.y - A.y) * (C.x - B.x) - (C.y - B.y) * (B.x - A.x);
}

bool Sort_Method(p P1, p P2)
{
	return Tan_of_Angle(points[1], P1, P2) < 0;
}

void Convex_Hull()
{
	stack[1] = points[1], stack[2] = points[2], stack_size = 2;
	for (int i = 3; i <= points_size; i++)
	{
		while (stack_size >= 2 && Tan_of_Angle(stack[stack_size - 1], stack[stack_size], points[i]) >= 0)
			stack_size--;
		stack[++stack_size] = points[i];
	}
}

void Print_Convex_Hull()
{
	out << stack_size << "\n";
	for (int i = 1; i <= stack_size; i++)
		out << stack[i].x << " " << stack[i].y << "\n";
}

void Control_Convex_Hull()
{
	sort(points + 2, points + 1 + points_size, Sort_Method);
	Convex_Hull();
	Print_Convex_Hull();
}

int main()
{
	out << setprecision(6) << fixed;
	Read_Data();
	Control_Convex_Hull();
	return 0;
}