Cod sursa(job #3299478)

Utilizator Mihai00700Mihai Ghetu Mihai00700 Data 7 iunie 2025 00:58:44
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int NMAX = 120001;
struct ura{
    double x,y;
    int parte;
}v[NMAX];

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;
}
int st[NMAX];
bool cmp(ura a, ura b){
    if(a.x < b.x){
        return true;
    }else{
        if(a.x == b.x){
            if(a.y < b.y){
                return true;
            }
            return false;
        }
        return false;
    }
}

int main() {
    int i,n, k;
    in>>n;
    for(i = 1;i<=n;i++){
        in>>v[i].x>>v[i].y;
    }
    sort(v + 1, v+n+1, cmp);
    ura prim = v[1], ultim = v[n];
    for(i = 2;i<=n - 1;i++){
        if(arie(prim, ultim, v[i]) < 0){
            v[i].parte = 2; // dedesubtul dreptei
        }else{
            v[i].parte = 1; // deasupra dreptei
        }
    }
    st[1] = 1;
    k = 1;
    for(i = 2;i<=n;i++){ //dedesubt
        if(v[i].parte == 2 || v[i].parte == 0){ 
            while(k>1 && arie(v[st[k - 1]],  v[st[k]], v[i]) <0){
                k--;
            }
            k++;
            st[k]=i;
        }
    }
    int ck = k;
    for(i = n-1;i>=1;i--){//deasupra
        if(v[i].parte == 1 || v[i].parte == 0){
            while(k>ck && arie(v[i],  v[st[k]], v[st[k-1]]) > 0){
                k--;
            }
            k++;
            st[k]=i;
        }
    }
    out<<k - 1<<"\n";
    for(i = 2;i<k;i++){
        out<<fixed<<setprecision(6)<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
    }
    out<<fixed<<setprecision(6)<<v[st[1]].x<<" "<<v[st[1]].y<<"\n";
    return 0;
}