Cod sursa(job #2854578)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 21 februarie 2022 15:07:23
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <deque>
#include <vector>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <cmath>
#include <climits>

#define MOD 104659

using namespace std ;

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

struct pct
{
    double x, y ;
};

pct v[120009], aux ;

int n ;

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

bool ord(pct a, pct b)
{
    if(det(aux, a, b) >= 0)return 0 ;
    return 1 ;
}
vector<pct> dq ;

int main()
{
    cin >> n ;

    for(int f = 1 ; f <= n ; f ++)
        cin >> v[f].x >> v[f].y ;

    /// inf convexa incepea din stanga jos

    int mn = 1 ;

    for(int f = 2 ; f <= n ; f ++)
        if(v[f].y < v[mn].y)mn = f ;

    swap(v[mn], v[1]) ;

    aux = v[1] ;

    /// sortam vectorul in functie de determinanti

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


    dq.push_back(v[1]) ;
    dq.push_back(v[2]) ;

    for(int f = 3 ; f <= n ; f ++)
    {
        while(dq.size() > 1 && det(dq[dq.size() - 2], dq[dq.size() - 1], v[f]) >= 0)
            dq.pop_back() ;

        dq.push_back(v[f]) ;
     }

    cout << dq.size() << endl ;

    for(int f = dq.size() - 1 ; f >= 0 ; f --)
        cout << fixed << setprecision(6) << dq[f].x << " " << dq[f].y << '\n' ;

    return 0 ;
}
/*
17
12.000000 1.000000
3.000000 -6.000000
6.000000 7.000000
-8.000000 12.000000
-12.000000 -11.000000
-6.000000 -3.000000
3.000000 10.000000
-10.000000 0.000000
7.000000 -13.000000
-14.000000 -6.000000
-12.000000 -7.000000
12.000000 -1.000000
-3.000000 -9.000000
11.000000 7.000000
1.000000 10.000000
6.000000 -5.000000
3.000000 11.000000
*/