Pagini recente » Cod sursa (job #304571) | Cod sursa (job #2764304) | Cod sursa (job #2980935) | Cod sursa (job #354119) | Cod sursa (job #3246998)
#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;
}