Cod sursa(job #1969402)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 18 aprilie 2017 14:10:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-12;
const int Nmax = 120005;

bool egale(double a, double b)
{
    a -= b;
    return a < eps && a > -eps;
}

struct Point
{
    double x, y;
    bool operator < (const Point &other) const
    {
        if(egale(x, other.x)) return y < other.y;
        return x < other.x;
    }
} a[Nmax];
int n, i, st[Nmax];
bool used[Nmax];

bool wrong(Point a, Point b, Point c)
{
    double arie;
    arie =  a.x * (b.y-c.y) + b.x * (c.y-a.y) + c.x * (a.y-b.y);
    return arie < eps;
}

void solve()
{
    int nr, i, add;
    memset(used, 0, sizeof(used));
    st[1] = 1; st[2] = 2; used[2] = 1; nr = 2;

    for(i=3, add=1; !used[1]; i += add)
    {
        if(i == n) add = -1;
        if(used[i]) continue;

        while(nr>=2 && wrong(a[st[nr-1]], a[st[nr]], a[i])) used[st[nr--]] = 0;

        st[++nr] = i;
        used[i] = 1;
    }

    printf("%d\n", nr-1);
    for(i=1; i<nr; ++i) printf("%.6lf %.6lf\n", a[st[i]].x, a[st[i]].y);
}

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

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

    solve();

    return 0;
}