Pagini recente » Diferente pentru utilizator/kriptmelody intre reviziile 3 si 2 | Cod sursa (job #1450839) | Cod sursa (job #3315714) | Cod sursa (job #1013684) | Cod sursa (job #2280037)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
#define NMAX 120004
using namespace std;
typedef pair<double, double> Point;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
Point P[NMAX]; //poligonul
Point S[NMAX]; //stiva
int vf;
void citire();
void sortare();
void afisare();
void convex_hull();
int main()
{
citire();
convex_hull();
afisare();
return 0;
}
void citire()
{int i;
fin >> n;
for (i = 0; i < n; ++i)
fin >> P[i].x >> P[i].y;
}
double CP(const Point& P1, const Point& P2, const Point& P3)
{
return (P2.x-P1.x)*(P3.y-P1.y)-(P2.y-P1.y)*(P3.x-P1.x);
}
int cmp(const Point& P1, const Point& P2)
{
return CP(P[0], P1, P2) < 0;
}
void sortare()
{int poz = 1, i;
for (i = 1; i < n; ++i)
if (P[i] < P[poz])
poz = i;
swap(P[0], P[poz]);
sort(P + 1, P + n, cmp);
}
void convex_hull()
{int i;
sortare();
S[1] = P[0]; S[2] = P[1]; vf = 2;
for (i=2; i < n; ++i)
{
while (vf >= 2 && CP(S[vf-1],S[vf],P[i])>=0)
vf--;
S[++vf] = P[i];
}
}
void afisare()
{int i;
fout << fixed;
fout << vf << "\n";
for (i = vf; i >= 1; --i)
fout<<setprecision(9)<<S[i].x<<" "<<S[i].y<<"\n";
}