Cod sursa(job #2384854)

Utilizator hristacheruxiRuxandra Hristache hristacheruxi Data 21 martie 2019 11:21:30
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <bits/stdc++.h>
using namespace std;
const int N = 120000;
struct coord{double x, y;}v[N], dr[N], st[N], s1[N], s2[N];

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

double arie(coord a, coord b, coord c)
{
    return a.x * b.y + b.x * c.y + a.y * c.x
        - b.y * c.x - c.y * a.x - b.x * a.y;
}

coord atribuire(double &a, double &b)
{
    coord nr;
    nr.x = a;
    nr.y = b;
    return nr;
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int n, 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);

    int k = 0, l = 0, A;
    dr[++k] = st[++l] = v[1];
    for (i = 2; i < n; i++)
    {
        coord a, b, c;

        a = atribuire(v[1].x, v[1].y);
        b = atribuire(v[n].x, v[n].y);
        c = atribuire(v[i].x, v[i].y);
        A = arie(a, b, c);

        if (A < 0)
            dr[++k] = c;
        else if (A > 0)
            st[++l] = c;
    }
    dr[++k] = st[++l] = v[n];

    //pe dreapta
    int m = 3;
    s1[1] = dr[1];
    s1[2] = dr[2];
    if (k >= 3)
    {
        s1[3] = dr[3];
        for (i = 4; i <= k; i++)
            if (arie(s1[m - 1], s1[m], dr[i]) > 0)
                s1[++m] = dr[i];
            else
                s1[m] = dr[i];
    }

    //pe stanga
    int w = 3;
    s2[1] = st[1];
    s2[2] = st[2];
    if (l >= 3)
    {
        s2[3] = st[3];
        for (i = 4; i <= l; i++)
            if (arie(s2[w - 1], s2[w], st[i]) < 0)
                s2[++w] = st[i];
            else
                s2[w] = st[i];
    }

    printf("%d\n", w + m - 2);
    for (i = 1; i <= m; i++)
        printf("%.12lf %.12lf\n", s1[i].x, s1[i].y);
    for (i = w - 1; i > 1; i--)
        printf("%.12lf %.12lf\n", s2[i].x, s2[i].y);

    return 0;
}