Cod sursa(job #1524081)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 13 noiembrie 2015 15:49:00
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013
#define x first
#define y second
#define eps 0.000000000001

using namespace std;

typedef pair<double, double> pereche;

int n, m, q, i;
pereche v[120005], r[120005];
double arie;
int stv[120005];

double det(pereche A, pereche B, pereche C)
{
    double r = A.x * B.y - A.y * B.x + B.x * C.y - C.x * B.y + C.x * A.y - A.x * C.y;
    return r;
}

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

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

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

    m = 2;
    stv[1] = 1;
    stv[2] = 2;
    for(i = 3; i <= n; i++)
    {
        while(m > 1 && det(v[ stv[m - 1] ], v[ stv[m] ], v[i]) < eps)
            m--;
        stv[++m] = i;
    }

    q = m;
    for(i = 1; i <= q; i++)
        r[i] = v[ stv[i] ];

    m = 2;
    stv[1] = n;
    stv[2] = n - 1;
    for(i = n - 2; i >= 1; i--)
    {
        while(m > 1 && det(v[ stv[m - 1] ], v[ stv[m] ], v[i]) < eps)
            m--;
        stv[++m] = i;
    }

    for(i = 1; i <= m; i++)
        r[ ++q ] = v[ stv[i] ];

    /*arie = 0;
    for(i = 1; i < q; i++)
        arie += v[i].x * v[i + 1].y - v[i].y * v[i + 1].x;

    arie /= 2.0;

    printf("%.12f", arie);*/

    printf("%d\n", q - 2);
    for(i = 1; i < q; i++)
    {
        if(r[i] == r[i - 1] && i > 1)
            continue;
        printf("%.6f %.6f\n", r[i].x, r[i].y);
    }

    return 0;
}