Cod sursa(job #2144320)

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

using namespace std;

const int NMax = 120005;

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

int N;

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

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

void Read()
{
    scanf("%d\n", &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 1.0 * (b.y-a.y)*(c.x-b.x) - (c.y-b.y)*(b.x-a.x);
}


struct Operator{
        bool operator()(Punct a, Punct b)
        {
            return UnghiPolar(v[1],a,b) > 0;
        }
} 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];
    }

    printf("%d", vf);


}

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

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

    return 0;
}