Cod sursa(job #1449766)

Utilizator caen1c a e n caen1 Data 10 iunie 2015 15:53:57
Problema Infasuratoare convexa Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.54 kb
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define NMAX 120000

struct point {
    double x, y;
};

static struct point P[NMAX];
static int S[NMAX], n, start, top;

static int polar_cmp(const void *a, const void *b)
{
    struct point p1 = *(const struct point *)a, p2 = *(const struct point *)b;
    double dir = P[start].x * p1.y + p1.x * p2.y + P[start].y * p2.x -
        p2.x * p1.y - p2.y * P[start].x - P[start].y * p1.x;

    return dir > 0 ? 1 : -1;
}

static int is_ccw(int p1, int p2, int p3)
{
    double dir = P[p1].x * P[p2].y + P[p2].x * P[p3].y + P[p1].y * P[p3].x -
        P[p3].x * P[p2].y - P[p3].y * P[p1].x - P[p1].y * P[p2].x;

    return (int) dir <= 0 ? 1 : 0;
}

int main(void)
{
    struct point p;
    double x, y, ymin = 1000000001.0;
    int i;

    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%lf %lf", &x, &y);
        P[i].x = x;
        P[i].y = y;
        if (y < ymin)
            start = i;
        else if (fabs(y - ymin) <= 0.000000000001)
            start = x < P[start].x ? i : start;
    }

    p = P[start];
    P[start] = P[0];
    P[0] = p;

    qsort(&P[1], n - 1, sizeof(struct point), polar_cmp);

    S[top++] = 0;
    S[top++] = 1;
    S[top++] = 2;
    for (i = 3; i < n; i++) {
        while (!is_ccw(S[top - 2], S[top - 1], i))
            --top;
        S[top++] = i;
    }

    printf("%d\n", top);
    for (i = 0; i < top; i++)
        printf("%lf %lf\n", P[S[i]].x, P[S[i]].y);

    return 0;
}