Cod sursa(job #3246959)

Utilizator andrei0simionAndrei Simion andrei0simion Data 4 octombrie 2024 21:40:21
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.57 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

struct Punct
{
	long double x = 0;
	long double y = 0;

	int parte = -2;
};

bool SortCoordonate(Punct a, Punct b)
{
	if (b.x < a.x)
		return false;
	else if (b.x == a.x && b.y < a.y)
		return false;
	else
		return true;
}

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

int nrPuncte;
Punct* puncte;
Punct valMinime;

long double Arie(Punct a, Punct b, Punct c)
{
	return (a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y);
}

int main()
{
	in >> nrPuncte;
	puncte = new Punct[nrPuncte];

	valMinime.x = 0;
	valMinime.y = 0;
	for (int i = 0; i < nrPuncte; i++)
	{
		in >> puncte[i].x;
		if (puncte[i].x < valMinime.x)
			valMinime.x = puncte[i].x;

		in >> puncte[i].y;
		if (puncte[i].y < valMinime.y)
			valMinime.y = puncte[i].y;
	}
	for (int i = 0; i < nrPuncte; i++)
	{
		puncte[i].x += valMinime.x;
		puncte[i].y += valMinime.y;
	}

	sort(puncte, puncte + nrPuncte, SortCoordonate);
	for (int i = 0; i < nrPuncte; i++)
	{
		long double arie = Arie(puncte[0], puncte[nrPuncte - 1], puncte[i]);
		if (arie < 0)
			puncte[i].parte = -1;
		else if (arie > 0)
			puncte[i].parte = 1;
		else if (arie == 0)
			puncte[i].parte = 0;
	}

	int nrElementeStiva = 0;
	int* stivaPuncte = new int[nrPuncte];

	for (int i = 0; i < nrPuncte; i++)
	{
		if (puncte[i].parte > 0)
			continue;

		if (nrElementeStiva < 2)
		{
			stivaPuncte[nrElementeStiva] = i;
			nrElementeStiva++;
			continue;
		}

		while (nrElementeStiva >= 2 && Arie(puncte[stivaPuncte[nrElementeStiva - 2]], puncte[stivaPuncte[nrElementeStiva - 1]], puncte[i]) < 0)
			nrElementeStiva--;
		stivaPuncte[nrElementeStiva] = i;
		nrElementeStiva++;
	}

	nrElementeStiva--;
	int offset = nrElementeStiva;
	for (int i = nrPuncte - 1; i >= 0; i--)
	{
		if (puncte[i].parte < 0)
			continue;

		if (nrElementeStiva < offset + 2)
		{
			stivaPuncte[nrElementeStiva] = i;
			nrElementeStiva++;
			continue;
		}

		while (nrElementeStiva >= offset + 2 && Arie(puncte[stivaPuncte[nrElementeStiva - 1]], puncte[stivaPuncte[nrElementeStiva - 2]], puncte[i]) > 0)
			nrElementeStiva--;
		stivaPuncte[nrElementeStiva] = i;
		nrElementeStiva++;
	}

	for (int i = 0; i < nrPuncte; i++)
	{
		puncte[i].x -= valMinime.x;
		puncte[i].y -= valMinime.y;
	}

	int nrPuncteVarfuri = nrElementeStiva - 1;
	out << nrPuncteVarfuri << '\n' << fixed << setprecision(6);
	for (int i = 0; i < nrPuncteVarfuri; i++)
	{
		out << puncte[stivaPuncte[i]].x << " " << puncte[stivaPuncte[i]].y << '\n';
	}

	delete[] stivaPuncte;
	delete[] puncte;
	return 0;
}