Pagini recente » Cod sursa (job #1725125) | Cod sursa (job #2313077) | Cod sursa (job #521957) | Cod sursa (job #1116472) | Cod sursa (job #979927)
Cod sursa(job #979927)
#include <cstdio>
#include <algorithm>
#include <stack>
#define x first
#define y second
using namespace std;
typedef pair <double, double> point;
const int NMAX = 120003;
point V[NMAX], S[NMAX];
double cross_product (const point &o, const point &a, const point &b) {
return (b.x - o.x) * (a.y - o.y) - (b.y - o.y) * (a.x - o.x);
}
bool comp (const point &a, const point &b) {
return cross_product (V[1], a, b) < 0;
}
int main () {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
int N, i, m = 1, b;
scanf ("%d", &N);
for (i = 1; i <= N; ++i) {
scanf ("%lf%lf", &V[i].x, &V[i].y);
if (V[m] > V[i])
m = i;
}
swap (V[1], V[m]);
sort (V + 2, V + N + 1, comp);
S[1] = V[1];
S[2] = V[2];
b = 2;
for (i = 3; i <= N; ++i) {
while (cross_product (V[i], S[b - 1], S[b]) > 0 && b >= 2)
--b;
S[++b] = V[i];
}
printf ("%d\n", b);
for (i = 1; i <= b; ++i)
printf ("%.6lf %.6lf\n", S[i].x, S[i].y);
}