Pagini recente » Cod sursa (job #2198703) | Cod sursa (job #2707862) | Cod sursa (job #2468491) | Cod sursa (job #1039956) | Cod sursa (job #979948)
Cod sursa(job #979948)
#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 += 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;
if (i == N)
k = -1;
else
if (i == 1)
break;
}
printf ("%d\n", b - 1);
for (i = 1; i < b; ++i)
printf ("%.6lf %.6lf\n", P[S[i]].x, P[S[i]].y);
}