Cod sursa(job #3362666)

Utilizator Dariuscriss72Popescu Darius Mihai Dariuscriss72 Data 11 august 2026 12:29:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb

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