Pagini recente » Cod sursa (job #3195572) | Cod sursa (job #3175501) | Cod sursa (job #1622416) | Cod sursa (job #1583240) | Cod sursa (job #2691398)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int NMAX = 120000;
const double EPS = 1e-12;
struct Punct
{
double x;
double y;
bool operator <(const Punct& other) const
{
if (this->x == other.x)
return this->y < other.y;
return this->x < other.x;
}
};
Punct punct[1 + NMAX];
int vf;
int stiva[1 + NMAX];
bool vizitat[1 + NMAX];
double ccw(const Punct& o, const Punct& a, const Punct& b)
{
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
in >> n;
for (int i = 1; i <= n; i++)
{
in >> punct[i].x >> punct[i].y;
}
sort(punct + 1, punct + 1 + n);
vf++;
stiva[vf] = 1;
for (int i = 2, pas = 1; i > 0; i += pas)
{
if (vizitat[i]) continue;
while (vf > 1 && ccw(punct[stiva[vf - 1]], punct[stiva[vf]], punct[i]) < EPS)
{
vizitat[stiva[vf]] = false;
vf--;
}
vf++;
stiva[vf] = i;
vizitat[i] = true;
if (i == n)
pas = -1;
//for (int j = 1; j <= vf; ++j)
// out << punct[stiva[j]].x << ' ' << punct[stiva[j]].y << ", ";
//out << '\n';
}
out << vf - 1 << '\n' << fixed << setprecision(6);
for (int i = 1; i < vf; i++)
{
out << punct[stiva[i]].x << ' ' << punct[stiva[i]].y << '\n';
}
return 0;
}