Cod sursa(job #3355628)

Utilizator Tudor_Iatagan2Iatagan Tudor Tudor_Iatagan2 Data 24 mai 2026 10:12:03
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct ura{
    double x, y;
    bool parte; ///true pentru dr-jos, false pentru st-sus
} v[120001], a, b;
int st[120001];
bool cmp( ura a, ura b ){
    if( a.x < b.x )
        return true;
    if( a.x > b.x )
        return false;
    if( a.y < b.y )
        return true;
    return false;
}
double arie( ura a, ura b, ura c ){
    return a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
}   ///functia returneaza dublul arii unui triunghi
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int main()
{
    int n, i;
    cin>>n;
    for( i = 1; i <= n; i++ )
        cin>>v[i].x>>v[i].y;
    sort( v + 1, v + n + 1, cmp );
    ///determinam partea fiecarui element
    //v[1] si v[n] sunt exceptiile, fiind in ambele parti simultan
    a=v[1];
    b=v[n];
    for( i = 2; i <= n - 1; i++ ){
        //daca aria < 0 atunci e in dr/josul liniei
        //aria != 0 pentru ca nu exista puncte coliniare
        //daca aria > 0 atunci e in st/susul liniei
        if( arie(a,b,v[i]) < 0 )
            v[i].parte=true;
        else
            v[i].parte=false;
    }
    ///acum facem partea true ( dr-jos )
    v[n].parte=true;
    st[1]=1;
    int k=1;
    for( i = 2; i <= n; i++ )
        if( v[i].parte == true ){
            while( k >= 2 && arie(v[st[k-1]],v[st[k]],v[i]) < 0 )
                k--;
            st[++k]=i;
        }
    ///acum facem parte false ( st-sus )
    int cpk=k;
    st[k]=n;
    v[1].parte=false;
    for( i = n - 1; i >= 1; i-- )
        if( v[i].parte == false ){
            while( k >= cpk + 1 && arie(v[st[k-1]],v[st[k]],v[i]) < 0 )
                k--;
            st[++k]=i;
        }
    cout<<k-1<<'\n';    ///st[k]==1
    for( i = 1; i < k; i++ )
        cout<<fixed<<setprecision(6)<<v[st[i]].x<<' '<<v[st[i]].y<<' '<<'\n';
    return 0;
}