Pagini recente » Cod sursa (job #110655) | Cod sursa (job #525070)
Cod sursa(job #525070)
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define maxn 120005
#define INF 1000000001
double x[maxn], y[maxn];
int n, start, indici[maxn], st[maxn];
bool cmp(int i, int j) {
return (double)(x[i] - x[start]) * (y[j] - y[start]) < (double)(x[j] - x[start]) * (y[i] - y[start]);
}
double sign(int i1, int i2, int i3) {
return (double) (x[i1] * y[i2] + x[i2] * y[i3] + x[i3] * y[i1] - y[i1] * x[i2] - y[i2] * x[i3] - y[i3] * x[i1]);
}
int main() {
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
scanf("%d", &n);
start = 0;
x[0] = INF;
y[0] = INF;
int i;
for (i = 1; i <= n; i++) {
scanf("%lf %lf", &x[i], &y[i]);
if (x[i] < x[start] || (x[i] == x[start] && y[i] < y[start]) > 0) start = i;
}
for (i = 1; i <= n; i++) {
if (i != start) {
indici[++indici[0]] = i;
}
}
sort(indici + 1, indici + n, cmp);
int k = 1;
st[k] = start;
for (i = 1; i <= indici[0]; i++) {
while (k >= 2 && sign(st[k - 1], st[k], indici[i]) > 0) --k;
st[++k] = indici[i];
}
printf("%d\n", k);
for (i = k; i >= 1; i--) {
printf("%lf %lf\n", x[st[i]], y[st[i]]);
}
return 0;
}