Pagini recente » Cod sursa (job #544221) | Cod sursa (job #1340815) | Cod sursa (job #274460) | Cod sursa (job #1174378) | Cod sursa (job #979947)
Cod sursa(job #979947)
#include <cstdio>
#include <algorithm>
#include <bitset>
#define x first
#define y second
using namespace std;
const int NMAX = 120003;
typedef pair <double, double> point;
bitset <NMAX> viz;
point P[NMAX];
int S[NMAX];
double cross_product (const point &o, const point &a, const point &b) {
return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
int main () {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
int N, i, b, k = 1;
scanf ("%d", &N);
for (i = 1; i <= N; ++i)
scanf ("%lf%lf", &P[i].x, &P[i].y);
sort (P + 1, P + N + 1);
S[1] = 1;
S[2] = 2;
b = 2;
for (i = 3; i >= 1; i += (k = (i == N ? -k : k))) {
if (viz[i])
continue;
while (cross_product (P[i], P[S[b - 1]], P[S[b]]) < 0 && b >= 2)
viz[S[b--]] = 0;
S[++b] = i;
viz[i] = 1;
}
printf ("%d\n", b - 1);
for (i = 1; i < b; ++i)
printf ("%.6lf %.6lf\n", P[S[i]].x, P[S[i]].y);
}