Cod sursa(job #2144289)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 26 februarie 2018 17:38:05
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMax = 120005;

struct Punct
{
    double x, y;
}v[NMax];

int N;

void Read()
{
    scanf("%d", &N);

    scanf("%lf %lf", &v[1].x, &v[1].y);
    for(int i=2; i<=N; ++i)
    {
        scanf("%lf %lf", &v[i].x, &v[i].y);
        if(v[i].y < v[1].y)
        {
            swap(v[i],v[1]);
        }

        else
            if(v[i].y==v[1].y && v[i].x < v[1].x)
                swap(v[1], v[i]);
    }
}

double UnghiPolar(Punct a, Punct b, Punct c)
{
    return (b.y-a.y)*(c.x-b.x) - (c.y-b.y)*(b.x-a.x);
}


struct Operator{
        bool operator()(Punct a, Punct b)
        {
            if(UnghiPolar(v[1],a,b) >= 0)
                return true;

            return false;
        }
} cmp;

Punct st[NMax];
int vf = 0;

void Graham()
{
    st[++vf] = v[1];
    st[++vf] = v[2];
    st[++vf] = v[3];

    for(int i=4; i<=N; ++i)
    {
        while(vf>=2 && UnghiPolar(st[vf-1], st[vf], v[i]) > 0);
            --vf;

        st[++vf] = v[i];
    }

    cout << vf << "\n";
    for(int i=1; i<=vf; ++i)
        cout << st[i].x << " " << st[i].y << "\n";
}

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

    Read();
    sort(v+2, v+N+1, cmp);

    Graham();
    return 0;
}