Pagini recente » Cod sursa (job #2954823) | Cod sursa (job #570613) | Cod sursa (job #2499929) | Cod sursa (job #1249878) | Cod sursa (job #780347)
Cod sursa(job #780347)
#include <cassert>
#include <cstdio>
#include <algorithm>
using namespace std;
struct puncte {
double x;
double y;
};
const int N = 120005;
const int INF = 0x3f3f3f3f;
int n, dim;
puncte p[N], stiva[N];
void cauta_stanga()
{
int poz = n + 1;
p[poz].x = p[poz].y = INF;
for (int i = 1; i <= n; ++i)
if (p[i].x < p[poz].x)
poz = i;
else if (p[i].x == p[poz].x && p[i].y < p[poz].y)
poz = i;
swap(p[1], p[poz]);
}
double tg(puncte a, puncte b)
{
return (double)(a.y - b.y) / (a.x - b.x);
}
int cmp(puncte a, puncte b)
{
return tg(a, p[1]) < tg(b, p[1]);
}
double det(puncte a, puncte b, puncte c)
{
return (double)a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y;
}
void infasuratoare()
{
sort(p + 2, p + n + 1, cmp);
dim = 1;
stiva[1] = p[1];
for (int i = 2; i <= n; ++i) {
stiva[++dim] = p[i];
while (dim >= 3 && det(stiva[dim - 2], stiva[dim - 1], stiva[dim]) < 0) {
stiva[dim - 1] = stiva[dim];
--dim;
}
}
}
int main()
{
assert(freopen("infasuratoare.in", "r", stdin));
assert(freopen("infasuratoare.out", "w", stdout));
assert(scanf("%d", &n) == 1);
for (int i = 1; i <= n; ++i)
assert(scanf("%lf %lf", &p[i].x, &p[i].y) == 2);
cauta_stanga();
infasuratoare();
printf("%d\n", dim);
for (int i = 1; i <= dim; ++i)
printf("%.12lf %.12lf\n", stiva[i].x, stiva[i].y);
}