Cod sursa(job #2156299)

Utilizator ioana.jianuIoana Jianu ioana.jianu Data 8 martie 2018 17:10:54
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

struct ura {double x, y;};
ura v[120001], st[120001], sol[120001];

bool cmp (ura a, ura b) {
    if (a.x < b.x)
        return true;
    else if (a.x > b.x)
        return false;
    else if (a.y < b.y)
        return true;
    else
        return false;
}

double semnarie (ura p1, ura p2, ura p3) {
    return p2.x * p1.y + p3.x * p2. y + p1.x * p3.y - p1.x * p2.y - p2.x * p3.y - p3.x * p1.y;
}

int main() {

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

    int n, vf1, vf, i;

    scanf ("%d", &n);
    for (i = 1; i <= n; i++)
        scanf ("%lf%lf", &v[i].x, &v[i].y);
    sort (v + 1, v + n + 1, cmp);

    vf = 0;
    for (i = 1; i < n; i++) {
        while (vf > 1 && semnarie (st[vf - 1], st[vf], v[i]) > 0)
            vf--;
        vf++;
        st[vf] = v[i];
    }

    for (i = 1; i <= vf; i++)
        sol[i] = st[i];
    vf1 = vf;

    vf = 0;
    for (i = n; i > 1; i--) {
        while (vf > 1 && semnarie (st[vf - 1], st[vf], v[i]) > 0)
            vf--;
        vf++;
        st[vf] = v[i];
    }

    printf ("%d\n", vf1 + vf);
    for (i = 1; i <= vf1; i++)
        printf ("%lf %lf\n", sol[i].x, sol[i].y);
    for (i = 1; i <= vf; i++)
        printf ("%lf %lf\n", st[i].x, st[i].y);


    return 0;
}