Pagini recente » Cod sursa (job #200399) | Cod sursa (job #1199585) | Cod sursa (job #235616) | Cod sursa (job #1727428) | Cod sursa (job #237314)
Cod sursa(job #237314)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
using namespace std;
#define INF 1000000000
#define EPS 1e-12
#define PDD pair<double, double>
#define x first
#define y second
int N, H;
PDD v[120005], P[120005];
inline int cmp(double a, double b)
{
if (a + EPS < b) return -1;
if (b + EPS < a) return +1;
return 0;
}
int cmp_PDD(const PDD &a, const PDD& b)
{
int r = cmp(a.x, b.x);
if (r != 0) return r == -1;
return cmp(a.y, b.y) == -1;
}
int semn(PDD a, PDD b, PDD c)
{
double A = a.y-b.y, B = b.x-a.x, C = a.x*b.y - b.x*a.y;
return cmp(A * c.x + B * c.y + C, 0);
}
int st[120005], uz[120005];
void ConvexHull()
{
int i, pas = +1, k;
sort(v+1, v+N+1, cmp_PDD);
uz[2] = 1; st[1] = 1; st[2] = 2; k = 2; i = 3;
while (!uz[1])
{
while (uz[i])
{
if (i == N)
pas = -1;
i += pas;
}
while (k >= 2 && semn(v[st[k-1]], v[st[k]], v[i]) == -1)
uz[st[k--]] = 0;
st[++k] = i; uz[i] = 1;
}
H = k-1;
for (i = 1; i <= H; ++i)
P[i] = v[st[i]];
P[H+1] = P[1];
}
int main()
{
int i, j;
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; ++i)
scanf("%lf %lf", &v[i].x, &v[i].y);
ConvexHull();
printf("%d\n", H);
// afisam varfurile in sens orar
srand(time(0));
j = rand() % (H-1) + 2;
for (i = j; i > 1; --i)
printf("%.6lf %.6lf\n", P[i].x, P[i].y);
for (i = H+1; i > j; --i)
printf("%.6lf %.6lf\n", P[i].x, P[i].y);
return 0;
}