Cod sursa(job #1796447)

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

using namespace std;

const int Nmax = 120000 + 5;

vector < point > v;
bool ok[Nmax];
int st[Nmax], n, i, dir, k;
double a, b;


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

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

    double det = a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;

    return ( cmp(det) );

}
void solve()
{

    ok[2] = true;

    st[1] = 1, st[2] = 2;
    i = 3, dir = 1, k = 2;

    while (!ok[1])
    {

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

        while (k >= 2 && sgn(v[st[k - 1]], v[st[k]], v[i]) < 0)
            ok[st[k--]] = false;

        st[++k] = i;
        ok[i] = true;

    }

    --k;

}

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

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

    v.push_back( make_pair(-INT_MAX, -INT_MAX) );

    for (i = 1; i <= n; ++i)
    {
        scanf("%lf %lf\n", &a, &b);
        v.push_back( make_pair (a, b) );
    }

    sort (v.begin(), v.end());

    solve();

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

    for (i = 1; i <= k; ++i)
        printf("%f %f\n", v[st[i]].x, v[st[i]].y);

    return 0;
}