Pagini recente » Cod sursa (job #2269274) | Cod sursa (job #1413723) | Cod sursa (job #1019674) | Cod sursa (job #3189894) | Cod sursa (job #1410908)
#include <fstream>
#include <math.h>
#include <iomanip>
using namespace std;
fstream f("infasuratoare.in", ios::in);
fstream g("infasuratoare.out", ios::out);
struct Point
{
double x, y;
};
const int nmax = 120010;
const double eps = 1e-12;
int n, i, size, s[nmax], viz[nmax];
Point a[nmax];
void read()
{
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 pos)
{
while ((size >= 2) && (cross_product(a[s[size - 1]], a[s[size]], a[pos]) < eps))
{
viz[s[size]] = 0;
size--;
}
size++;
s[size] = pos;
viz[pos] = 1;
}
void quickSort(int li, int ls)
{
int i = li, j = ls;
int mij = (i + j) / 2;
Point aux;
while (i <= j)
{
while ((a[i].x < a[mij].x) || ((a[i].x == a[mij].x) && (a[i].y < a[mij].y))) i++;
while ((a[j].x > a[mij].x) || ((a[j].x == a[mij].x) && (a[j].y > a[mij].y))) j--;
if (i <= j)
{
aux = a[i];
a[i] = a[j];
a[j] = aux;
i++; j--;
}
}
if (li < j) quickSort(li, j);
if (i < ls) quickSort(i, ls);
}
int main()
{
read();
quickSort(1, n);
s[1] = 1;
s[2] = 2;
size = 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 << size - 1 << '\n';
g << fixed << setprecision(12);
for (i = 1; i < size; i++) g << a[s[i]].x << " " << a[s[i]].y << "\n";
return 0;
}