Cod sursa(job #2531654)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 26 ianuarie 2020 15:57:19
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.4 kb
#include <fstream>
#include <deque>
#include <algorithm>

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

struct Punct
{
    long double x, y;
};

deque < Punct > H;
Punct v[120005], vv[120005], Inceput;
int n;

void citire_si_gasirea_primelor_2_puncte();
bool crt ( Punct a, Punct b );
bool triunghi_in_sens_trigonometric ( Punct a, Punct b, Punct c );

int main()
{
    Punct prec1, prec2;
    int i;

    citire_si_gasirea_primelor_2_puncte();
    prec1 = H.front();
    prec2 = Inceput;
    for ( i = 1 ; i <= n ; i++ )
    {
        while ( triunghi_in_sens_trigonometric ( prec2, prec1, v[i] ) == 0 )
        {
            H.pop_front();
            prec1 = prec2;
            H.pop_front();
            prec2 = H.front();
            H.push_front ( prec1 );
        }
        prec2 = prec1;
        prec1 = v[i];
        H.push_front ( v[i] );
    }

    fout << H.size() << '\n';
    while ( H.empty() == 0 ) fout << H.back().x << ' ' << H.back().y << '\n', H.pop_back();

    return 0;
}

void citire_si_gasirea_primelor_2_puncte()
{
    Punct x;
    int i, j;

    fin >> n >> v[1].x >> v[1].y;
    j = 1;
    for ( i = 2 ; i <= n ; i++ )
    {
        fin >> v[i].x >> v[i].y;
        if ( v[i].x < v[j].x || ( v[i].x == v[j].x && v[i].y < v[j].y ) ) j = i;
    }

    Inceput = v[j];
    for ( i = j ; i < n ; i++ ) v[i] = v[i+1];
    n--;

    sort ( v + 1, v + n + 1, crt );
    v[0] = v[n];
    v[n+1] = v[1];
    v[n+2].x = v[n+2].y = 1000000001;
    j = n + 2;
    for ( i = 1 ; i <= n ; i++ ) if ( triunghi_in_sens_trigonometric ( Inceput, v[i], v[i-1] ) == 1 && triunghi_in_sens_trigonometric ( Inceput, v[i], v[i-1] ) == 1 ) if ( v[i].x < v[j].x || ( v[i].x == v[j].x && v[i].y < v[j].y ) ) j = i;
    for ( i = j ; i <= n ; i++ ) vv[i-j+1] = v[i];
    for ( i = 1 ; i < j ; i++ ) vv[i+n-j] = v[i];
    for ( i = 1 ; i <= n ; i++ ) v[i] = vv[i];

    for ( i = 1; i < n ; i++ ) v[i] = v[i+1];
    n--;

    H.push_front ( Inceput );
    H.push_front ( vv[1] );
}

bool crt ( Punct a, Punct b )
{
    if ( triunghi_in_sens_trigonometric ( Inceput, a, b ) == 1 ) return 1;

    return 0;
}

bool triunghi_in_sens_trigonometric ( Punct a, Punct b, Punct c )
{
    b.x -= a.x;
    b.y -= a.y;
    c.x -= a.x;
    c.y -= a.y;
    if ( b.x * c.y - b.y * c.x < 0 ) return 0;

    return 1;
}