Cod sursa(job #525070)

Utilizator judy_kCristina Petrovici judy_k Data 24 ianuarie 2011 00:28:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#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;
}