Cod sursa(job #2871088)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 12 martie 2022 20:54:16
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits>
#include <iomanip>
#include <cmath>

#define MOD 666013
#define INT_MAX 1000000000

using namespace std ;

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

/// la intersectia a doua segmente avem doua optiuni
/// aflam intersectia dreptelor dupa care verificam daca punctul respectiv apartine segmentelor
/// calculam determinantii in stanga si dreapta unui segment si vedem sa aiba semne diferite

struct pct
{
    double x, y ;
};

pct v[100009] ;

double d(pct a, pct b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) ;
}

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

int n ;

bool ord(pct a, pct b)
{
    return det(v[1], a, b) > 0 ;
}

bool trebe_scos(pct a, pct b, pct c)
{
    return det(a, b, c) <= 0 ;
}

int main()
{
    cin >> n ;

    for(int f = 1 ; f <= n ; f ++)
    {
        pct a ;

        cin >> a.x >> a.y ;

        v[f] = a ;
    }

    int mn = 1 ;

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

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

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

    vector<pct> dq ;

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

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

        dq.push_back(v[f]) ;
    }

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

    for(int f = 0 ; f < dq.size() ; f ++)
        cout << dq[f].x << " " << dq[f].y << "\n" ;

    return 0 ;
}
/// 1990