Cod sursa(job #2118518)

Utilizator antanaAntonia Boca antana Data 30 ianuarie 2018 18:41:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <algorithm>

#define EPS (1e-12)
#define MAXN 120002

using namespace std;

int n, k;

struct point{
    double x, y;

    bool operator < (const point &aux) const {
        if(x == aux.x)
            return (y < aux.y);
        return (x < aux.x);
    }
}v[MAXN], stk[MAXN];

inline double area(const point &a, const point &b, const point &c){
    return a.x*b.y - b.x*a.y + b.x*c.y - c.x*b.y + c.x*a.y - a.x*c.y;
}

bool compare(const point &a, const point &b){
    return  area(v[1], a, b) > 0;
}

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

    int i, pos;

    scanf("%d", &n);

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

    pos = 1;
    for(i=2; i<=n; ++i)
        if(v[i] < v[pos])
            pos = i;

    swap(v[1], v[pos]);

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

    stk[1] = v[1];
    stk[2] = v[2];
    k = 2;

    for(i=3; i<=n; ++i)
    {
        while(k > 2 && area(stk[k-1], stk[k], v[i]) < 0)
            k--;
        stk[++k] = v[i];
    }

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

    for(i=1; i<=k; ++i)
        printf("%.6lf %.6lf\n", stk[i].x, stk[i].y);


    return 0;
}