Cod sursa(job #3292321)

Utilizator vladsoartavlad sofronea vladsoarta Data 7 aprilie 2025 21:15:33
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define double long double
#define int long long
using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

int n,i;
struct point{
double x,y;
bool operator <(point b)const{
    if(x!=b.x)
        return x < b.x;
    return y < b.y;
}
}v[120001];

double cross_product(const point& A, const point& B, const point& C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
bool cmp(point a,point b)//sortare panta
{
    return cross_product(v[1],a,b)< 0;
}

int32_t main()
{
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;

    }
    int pos=1;
    for(i=2;i<=n;i++)
        if(v[i] < v[pos])
            pos = i;
    swap(v[pos],v[1]);
        sort(v+2,v+1+n,cmp);

    vector<int>stk;
    stk.push_back(1);
    stk.push_back(2);
    for(i=3;i<=n;i++){
        while(stk.size() > 2 && cross_product(v[stk[stk.size()-2]],v[stk[stk.size()-1]],v[i]) > 0){
            stk.pop_back();
        }
        stk.push_back(i);
    }
    cout<<stk.size()<<'\n';
    for(int h=stk.size()-1;h>=0;h--)
        cout<<fixed<<setprecision(9)<<v[stk[h]].x<<" "<<v[stk[h]].y<<'\n';
    return 0;
}