Cod sursa(job #2268450)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 24 octombrie 2018 20:29:10
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.06 kb
// Teoretic Pure - Convex HULL.cpp : Defines the entry point for the console application.
//

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

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

using namespace std;

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

struct punct
{
	double x, y;
};
punct puncte[120005], convex_h[120005];
int nr_puncte, stack_level = 0;
int maximum = 0;
punct lowest_p = { 1000000000, 1000000000 };

void Read_Data()
{
	in >> nr_puncte;
	for (int i = 1; i <= nr_puncte; i++)
		in >> puncte[i].x >> puncte[i].y;
}

inline bool Compare_Criteria(punct a, punct b)
{
	if (a.x == b.x) return a.y < b.y ? 1 : 0;
	return a.x < b.x ? 1 : 0;
}

inline bool Check_Identic(punct a, punct b)
{
	if (a.x == b.x && a.y == b.y) return true;
	return false;
}

void Swap_Points(punct &a, punct &b)
{
	punct aux = a;
	a = b;
	b = aux;
}

double Position_of_Points(punct a, punct b, punct c)
{
	// <0 - anticlockwise
	// ==0 - colinear
	// >0 - clockwise
	double slope_AB = (double)(a.y - b.y) / (double)(a.x - b.x);
	double slope_BC = (double)(b.y - c.y) / (double)(b.x - c.x);
	// Difference between x coordinates can be null, so we expand the ecuation
	return ((double)(b.y - a.y)*(c.x - b.x) - (c.y - b.y)*(b.x - a.x));
}

inline bool Sort_M(punct a, punct b)
{
	double val = Position_of_Points(lowest_p, a, b);
	return val < 0;
}

void Convex_HULL()
{
	for (int i = 1; i < nr_puncte; i++)
	for (int j = i + 1; j <= nr_puncte; j++)
	{
		punct a = puncte[i], b = puncte[j];
		// Ecuatie: Ax+By+C=0
		double A = 0, B = 0, C = 0;
		A = b.y - a.y;
		B = a.x - b.x;
		C = a.y * b.x - a.x * b.y;
		int to_left = 0, to_right = 0;
		for (int k = 1; k <= nr_puncte; k++)
		{
			double val = A * puncte[k].x + B * puncte[k].y + C;
			if (val < 0) to_left++;
			if (val > 0) to_right++;
		}
		if (to_left == nr_puncte - 2 || to_right == nr_puncte - 2)
		{
			convex_h[++stack_level] = a, convex_h[++stack_level] = b;
		}
	}
	sort(convex_h + 1, convex_h + 1 + stack_level, Compare_Criteria);
	for (int i = 1; i < stack_level; i++)
	if (Check_Identic(convex_h[i], convex_h[i + 1])) convex_h[i] = { 0, 0 };
	for (int i = 1; i <= stack_level; i++)
	if (convex_h[i].x != 0 || convex_h[i].y != 0)
	{
		int k = i;
		while (k > 1 && convex_h[k - 1].x == 0 && convex_h[k - 1].y == 0)
			convex_h[--k] = convex_h[k + 1], convex_h[k + 1] = { 0, 0 };
		maximum = k;
	}
	out << maximum << "\n";
}

void Sort_Anti_ClockWise()
{
	out << setprecision(6) << fixed;
	int p = 0;
	for (int i = 1; i <= maximum; i++)
	{
		if (convex_h[i].x < lowest_p.x) lowest_p = convex_h[i], p = i;
		else if (convex_h[i].x == lowest_p.x)
		{
			if (convex_h[i].y < lowest_p.y) 
				lowest_p = convex_h[i], p = i;
		}
	}
	Swap_Points(convex_h[1], convex_h[p]);
	sort(convex_h + 2, convex_h + 1 + maximum, Sort_M);
	for (int i = 1; i <= maximum; i++)
		out << convex_h[i].x << " " << convex_h[i].y << "\n";
}
 
int main()
{
	Read_Data();
	Convex_HULL();
	Sort_Anti_ClockWise();
	return 0;
}