Cod sursa(job #3246998)

Utilizator andrei0simionAndrei Simion andrei0simion Data 5 octombrie 2024 00:59:27
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

	int parte = -2;
};

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

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

int nrPuncte;
Punct* puncte;

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

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

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

	sort(puncte, puncte + nrPuncte, SortCoordonate);
	for (int i = 0; i < nrPuncte; i++)
	{
		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;
	}
	puncte[0].parte = 0;
	puncte[nrPuncte - 1].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 - 2]], puncte[stivaPuncte[nrElementeStiva - 1]], puncte[i]) < 0)
			nrElementeStiva--;
		stivaPuncte[nrElementeStiva] = i;
		nrElementeStiva++;
	}

	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;
}