Pagini recente » Cod sursa (job #207681) | Cod sursa (job #113168) | Cod sursa (job #706422) | Cod sursa (job #1758268) | Cod sursa (job #3246959)
#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;
}