Pagini recente » Cod sursa (job #2930127) | Cod sursa (job #1939245) | Cod sursa (job #2821506) | Cod sursa (job #2383771) | Cod sursa (job #573316)
Cod sursa(job #573316)
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
#define Nmax 120010
struct punct {
double x, y;
} P[Nmax];
int n, N;
int Stiva[Nmax], viz[Nmax];
int cmp (const punct &a, const punct &b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
int determ (long double x1, long double y1, long double x2, long double y2, long double x3, long double y3) {
if ((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) < 0) return 1;
return 0;
}
void infasuratoare () {
int i, stp;
Stiva[++N] = 1;
Stiva[++N] = 2;
viz[2] = 1; i = 2; stp = 1;
while (!viz[1]) {
if (i == n) stp = -1;
i+= stp;
while (viz[i]) {
if (i == n) stp = -1;
i+= stp;
}
while (N > 1 && !determ (P[Stiva[N]].x, P[Stiva[N]].y, P[Stiva[N-1]].x, P[Stiva[N-1]].y, P[i].x, P[i].y))
viz[Stiva[N--]] = 0;
viz[i] = 1;
Stiva[++N] = i;
}
printf ("%d\n", N-1);
for (i = 1; i < N; i++)
printf ("%lf %lf\n", P[Stiva[i]].x, P[Stiva[i]].y);
}
int main () {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
scanf ("%d", &n);
for (int i = 1; i <= n; i++)
scanf ("%lf %lf", &P[i].x, &P[i].y);
sort (P + 1, P + n + 1, cmp);
infasuratoare ();
return 0;
}