Cod sursa(job #3246873)

Utilizator tudorhTudor Horobeanu tudorh Data 4 octombrie 2024 17:27:48
Problema Infasuratoare convexa Scor 0
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 2.99 kb
#include <bits/stdc++.h>

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