Cod sursa(job #2261005)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 15 octombrie 2018 20:25:18
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
// Infasuratoare convexa - teorie.cpp : Defines the entry point for the console application.
//
#include <fstream>
#include <algorithm>

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

using namespace std;

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

struct coord
{
	double x, y;
};
coord points[ARR_SIZE], stack[ARR_SIZE], first_point = {1000000000, 1000000000};
int puncte, coresp;

bool Sort_Criteria(coord f2, coord f3)
{
	double value = (double)(f2.y - first_point.y)*(f3.x - f2.x) - (f3.y - f2.y)*(f2.x - first_point.x);
	return value < 0;
}

double Position_of_Points(coord a, coord b, coord 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));
}

void Swap_Points(coord &p1, coord &p2)
{
	coord aux = p1;
	p1 = p2;
	p2 = aux;
}

void Read_Data()
{
	in >> puncte;
	for (int i = 1; i <= puncte; i++)
	{
		in >> points[i].x >> points[i].y;
		// Find most low point
		if (points[i].x < first_point.x)
			first_point = points[i], coresp = i;
		else if (points[i].x == first_point.x)
		if (points[i].y < first_point.y)
			first_point = points[i], coresp = i;
	}
	swap(points[1], points[coresp]);
	sort(points + 2, points + 1 + puncte, Sort_Criteria);
}

void Check_Daca_Ce_Vor_Dusmanii_S_a_Adeverit()
{
	stack[1] = points[1];
	stack[2] = points[2];
	int nivel = 2;
	for (int i = 3; i <= puncte; i++)
	{
		while (nivel >= 2 && Position_of_Points(stack[nivel - 1], stack[nivel], points[i]) > 0)
			nivel--;
		stack[++nivel] = points[i];
	}
	out << nivel << "\n";
	for (int i = 2; i <= nivel; i++)
		out << stack[i].x << " " << stack[i].y << "\n";
	out << stack[1].x << " " << stack[1].y << "\n";
}

int main()
{
	Read_Data();
	//out << puncte << "\n";
	//for (int i = 1; i <= puncte; i++)
		//out << points[i].x << " " << points[i].y << "\n";
	//out << "\n";
	Check_Daca_Ce_Vor_Dusmanii_S_a_Adeverit();
	return 0;
}