Pagini recente » Cod sursa (job #2066107) | Cod sursa (job #2754422) | Cod sursa (job #1321754) | Cod sursa (job #3189308) | Cod sursa (job #1411152)
#include <fstream>
#include <math.h>
#include <iomanip>
#include <algorithm>
using namespace std;
fstream f("infasuratoare.in", ios::in);
fstream g("infasuratoare.out", ios::out);
struct Point
{
double x, y;
bool operator < (const Point &p) const
{
if (p.x > x) return true;
if (p.x < x) return false;
if (p.y > y) return true;
return false;
}
};
const int nmax = 120010;
const double eps = 1e-12;
int n, head, s[nmax], viz[nmax];
Point a[nmax];
void read()
{
int i;
f >> n;
for (i = 1; i <= n; i++)
{
f >> a[i].x >> a[i].y;
}
}
double cross_product(Point A, Point B, Point C)
{
return (C.y - A.y) * (B.x - A.x) - (B.y - A.y) * (C.x - A.x);
}
void convex_hull(int poz)
{
while ((head >= 2) && (cross_product(a[s[head - 1]], a[s[head]], a[poz]) < eps))
{
viz[s[head]] = 0;
head--;
}
head++;
s[head] = poz;
viz[poz] = 1;
}
int main()
{
int i;
read();
sort(a + 1, a + n + 1);
s[1] = 1;
s[2] = 2;
head = 2;
viz[2] = 1;
for (i = 3; i < n; i++) if (!viz[i]) convex_hull(i);
for (i = n; i >= 1; i--) if (!viz[i]) convex_hull(i);
g << head - 1 << '\n';
g << fixed << setprecision(12);
for (i = 1; i < head; i++) g << a[s[i]].x << " " << a[s[i]].y << "\n";
return 0;
}