Cod sursa(job #3354653)

Utilizator Tudor_Iatagan2Iatagan Tudor Tudor_Iatagan2 Data 19 mai 2026 17:30:38
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
//sursa neterminata
#include <fstream>
#include <algorithm>
using namespace std;
struct ura{
    double x, y;
    bool parte; ///true pentru dr-jos, false pentru st-sus
} v[120001], st[120001];
ura pct1[120001], pct2[120001]; ///partea true, respectiv partea false
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;
        ///aducem fiecare element in cadranul 1
        v[i].x+=1000000000;
        v[i].y+=1000000000;
    }
    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]=v[1];
    i=2;
    while( v[i].parte == false && i <= n - 1 )
        i++;
    if( i != n )
    st[2]=v[i];
    int k=2;
    for( i = i + 1; i <= n - 1; i++ )
        if( v[i].parte == true ){
            x1=v[k-1].x;
            y1=v[k-1].y;
            x2=v[k].x;
            y2=v[k].y;
            while( arie(x1,y1,x2,y2,v[i].x,v[i].y) < 0 && k >= 2 ){
                k--;
                if( k >= 2 ){
                    x1=v[k-1].x;
                    y1=v[k-1].y;
                    x2=v[k].x;
                    y2=v[k].y;
                }
            }
            st[++k]=v[i];
        }
    return 0;
}