Cod sursa(job #1912284)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 8 martie 2017 00:34:45
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

#define x first
#define y second

#define pdd pair < double , double >

using namespace std;

const int NMax = 120005;
int N;

pdd v[NMax];
vector < pdd > ST;

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

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

int Det(pdd a, pdd b, pdd c)
{
    return (a.x*b.y + a.y*c.x + b.x*c.y - b.y*c.x - c.y*a.x - a.y*b.x );
}

void Minim()
{
    for(int i=2; i<=N; ++i)
        if(v[i] < v[1])
            swap(v[i], v[1]);
}

struct Comparator
{
        bool operator()(pdd a, pdd b)
        {
            return Det(v[1],a,b) > 0;
        }
} cmp;

void Sortare()
{
    sort(v+2, v+N+1, cmp);
}

void Algorithm()
{
    for(int i=1; i<=N; ++i)
    {

        while(ST.size() >=2 && Det(ST[ST.size()-2], ST[ST.size()-1], v[i]) < 0)
            ST.pop_back();

        ST.push_back(v[i]);
    }
}

void Print()
{
    printf("%d\n", ST.size());

    for(vector< pdd >::iterator it = ST.begin(); it != ST.end(); ++it)
        printf("%.6lf %.6lf\n", it->x, it->y);

}

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

    Read();
    Minim();
    Sortare();
    Algorithm();
    Print();

    return 0;
}