Cod sursa(job #3363694)

Utilizator Dariuscriss72Popescu Darius Mihai Dariuscriss72 Data 21 august 2026 13:18:49
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb

#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct per{
    double x;
    double y;
}a[120005],hull[220005];
bool verif(per a,per b,per c){
    double aux=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    if(aux<=0){
        return false;
    }
    return true;
}
#define cin f
#define cout g 
signed main()
{
    int N,i;
    cin>>N;
    for(i=1;i<=N;i++){
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+1+N,[](per a,per b){
        if(a.y!=b.y){
            return a.y<b.y;
        }
        return a.x<b.x;
    });
    int poz=1;
    for(i=1;i<=N;i++){
        while(poz>2 && verif(hull[poz-2],hull[poz-1],a[i])==false){
           poz--;
        } 
        hull[poz++]=a[i];
    }
    int lim=poz;
    for(i=N-1;i>=1;i--){
        while(poz>lim && verif(hull[poz-2],hull[poz-1],a[i])==false){
           poz--;
        }
        hull[poz++]=a[i];
    }
    cout<<poz-2<<"\n";
    for(i=1;i<=poz-2;i++){
        cout<<fixed<<setprecision(6)<<hull[i].x<<" "<<hull[i].y<<"\n";
    }
    return 0;
}