Cod sursa(job #2854675)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 21 februarie 2022 17:10:49
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream cin("infasuratoare.in") ;
ofstream cout("infasuratoare.out") ;

/// se sorteaza punctele
/// plecam de la elem cel mai st si cel mai jos
/// se ia elem cu cea mai mare panta fata de primul punct
/// acum luam puncte in ordinea trigonometrica crescator dupa unghiul cu latura precedenta

/// comparatorul trebe sa zica ca determinantul format de punctele a, b, c sa fie negativ

struct pct
{
    double x = 0, y = 0 ;
};

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

pct mnx, v[120009] ;

bool ord(pct a, pct b)
{
    return (determinant_3_puncte(mnx, a, b) > 0) ;
}

bool cant_add(pct a, pct b, pct c)
{
    return (determinant_3_puncte(a, b, c) < 0) ;
}

int main()
{
    int n ;

    cin >> n ;

    int mn = 1 ;

    for(int f = 1 ; f <= n ; f ++)
    {
        double a, b ;

        cin >> a >> b ;

        v[f].x = a ;
        v[f].y = b ;

        /// caut cel stanga jos

        if(v[f].x < v[mn].x)mn = f ;
            else if(v[f].x == v[mn].x && v[f].y < v[mn].y)mn ;

    }

    mnx = v[mn] ;

    for(int f = 1, t = 0 ; f <= n ; f ++)
        if(f != mn)v[++ t] = v[f] ;

    sort(v + 1, v + n, ord) ;

    vector<pct> fin ;

    fin.push_back(mnx) ;

    fin.push_back(v[1]) ;

    for(int f = 2 ; f < n ; f ++)
    {

        while(cant_add(fin[fin.size() - 2], fin.back() , v[f]))
            fin.pop_back() ;

        fin.push_back(v[f]) ;
    }
    cout << fin.size() << endl ;

    for(int f = 0 ; f < fin.size() ; f ++)
        cout << fixed << setprecision(6) << fin[f].x << " " << fin[f].y << '\n' ;

    return 0;
}