Cod sursa(job #3246947)

Utilizator andrei0simionAndrei Simion andrei0simion Data 4 octombrie 2024 21:05:46
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.75 kb
#include <iostream>
#include <ifstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

	int parte = -2;
	bool varf = false;
};

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++;
	}
	for (int i = 0; i < nrElementeStiva; i++)
		puncte[stivaPuncte[i]].varf = true;

	nrElementeStiva = 0;
	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++;
	}
	for (int i = 0; i < nrElementeStiva; i++)
		puncte[stivaPuncte[i]].varf = true;

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

	int nrPuncteVarfuri = 0;
	for (int i = 0; i < nrPuncte; i++)
	{
		if (puncte[i].varf)
			nrPuncteVarfuri++;
	}
	out << nrPuncteVarfuri << '\n' << fixed << setprecision(6);
	for (int i = 0; i < nrPuncte; i++)
	{
		if (puncte[i].varf)
			out << puncte[i].x << " " << puncte[i].y << '\n';
	}

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