Cod sursa(job #2262665)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 17 octombrie 2018 18:05:41
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
// Empowersoft 2017 - Archie - Convex HULL.cpp : Defines the entry point for the console application.
//

#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

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

using namespace std;

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

struct p
{
	double x, y;
};
p points[NMAX], stiva[NMAX], reper_point = { 1000000001, 1000000001 };
int puncte, reper_value, nivel;

double Check_Position_Points(p p1, p p2, p p3)
{
	double distance = (double)(p2.y - p1.y)*(p3.x - p2.x) - (double)(p3.y - p2.y)*(p2.x - p1.x);
	return distance;
}
void Swap_Points(p &a, p &b)
{
	p aux = a;
	a = b;
	b = aux;
}
bool Sort_Criterium(p a, p b)
{
	return Check_Position_Points(reper_point, a, b) < 0;
}
double Max(double a, double b)
{
	return a > b ? a : b;
}

void Read_Data()
{
	in >> puncte;
	for (int i = 1; i <= puncte; i++)
	{
		in >> points[i].x >> points[i].y;
		if (points[i].x < reper_point.x)
			reper_point = points[i], reper_value = i;
		else if (points[i].x == reper_point.x)
		if (points[i].y < reper_point.y)
			reper_point = points[i], reper_value = i;
	}
	Swap_Points(points[reper_value], points[1]);
	sort(points + 2, points + 1 + puncte, Sort_Criterium);
}

void Convex_HULL()
{
	stiva[1] = points[1];
	stiva[2] = points[2];
	nivel = 2;
	for (int i = 3; i <= puncte; i++)
	{
		while (nivel >= 2 && Check_Position_Points(stiva[nivel-1], stiva[nivel], stiva[i]) >= 0)
			nivel--;
		stiva[++nivel] = points[i];
	}
}

void Solve_Task()
{
	out << nivel << "\n";
	for (int i = 1; i <= nivel; i++)
		out << stiva[i].x << " " << stiva[i].y << "\n";
}

int main()
{
	out << setprecision(8) << fixed;
	Read_Data();
	Convex_HULL();
	Solve_Task();
	return 0;
}