Cod sursa(job #1603369)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 17 februarie 2016 14:03:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
# include <bits/stdc++.h>
# define point pair < double , double >
# define x first
# define y second
# define eps 1e-12

using namespace std;

const int Nmax = 120000 + 5;
bool ok[Nmax];

int n, k, stiv[Nmax];
double X, Y;
pair <double, double> a[Nmax];

int cmp (double a, double b) {
    if (a + eps < b) return -1;
    if (b + eps < a) return 1;
    return 0;
}

int semn (point a, point b, point c) {

    return cmp (a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y, 0);
}


void sol () {

    stiv[1] = 1, stiv[2] = 2, k = 2;

    ok[2] = true;
    int q = 1, i = 3;

    while (!ok[1]) {

        while (ok[i]) {
            if (i == n) q *= -1;
            i += q;
        }

        while (k >= 2 && semn (a[stiv[k - 1]], a[stiv[k]], a[i]) == -1)
           ok[stiv[k--]] = false;

        stiv[++k] = i;
        ok[i] = true;
    }

}
int main ()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d\n", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%lf %lf\n", &a[i].x, &a[i].y);
    }

    sort (a + 1, a + n + 1);

    sol();

    printf("%d\n", k - 1);

    for (int i = 2; i <= k; ++i)
        printf("%lf %lf\n", a[stiv[i]].x, a[stiv[i]].y);


    return 0;

}