Cod sursa(job #3354670)

Utilizator Tudor_Iatagan2Iatagan Tudor Tudor_Iatagan2 Data 19 mai 2026 17:51:40
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.65 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];
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( double x1, double y1, double x2, double y2, double x3, double y3 ){
    return (x1*y2+x2*y3+x3*y1-x3*y2-x1*y3-x2*y1)/2;
}   ///functia returneaza aria 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
    int x1=v[1].x, y1=v[1].y, x2=v[n].x, y2=v[n].y;
    for( i = 2; i <= n - 1; i++ ){
        ///dreapta AB; A(x1,y1) si B(x2,y2)
        //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(x1,y1,x2,y2,v[i].x,v[i].y) < 0 )
            v[i].parte=true;
        else
            v[i].parte=false;
    }
    ///acum facem partea true ( dr-jos ), punand punctele in vectorul pct1[]
    v[n].parte=true;
    st[1]=1;
    int k=1;
    for( i = 2; i <= n; i++ )
        if( v[i].parte == true ){
            x1=v[st[k-1]].x;
            y1=v[st[k-1]].y;
            x2=v[st[k]].x;
            y2=v[st[k]].y;
            while( k >= 2 && arie(x1,y1,x2,y2,v[i].x,v[i].y) < 0 ){
                k--;
                if( k >= 2 ){
                    x1=v[st[k-1]].x;
                    y1=v[st[k-1]].y;
                    x2=v[st[k]].x;
                    y2=v[st[k]].y;
                }
            }
            st[++k]=i;
        }
    int ck=k;
    st[k]=n;
    v[1].parte=false;
    for( i = n - 1; i >= 1; i-- )
        if( v[i].parte == false ){
            x1=v[st[k-1]].x;
            y1=v[st[k-1]].y;
            x2=v[st[k]].x;
            y2=v[st[k]].y;
            while( k >= ck + 1 && arie(x1,y1,x2,y2,v[i].x,v[i].y) < 0 ){
                k--;
                if( k >= 2 ){
                    x1=v[st[k-1]].x;
                    y1=v[st[k-1]].y;
                    x2=v[st[k]].x;
                    y2=v[st[k]].y;
                }
            }
            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;
}