Cod sursa(job #3283869)

Utilizator IleaIlea Bogdan Ilea Data 10 martie 2025 16:59:27
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;

#define NMAX 120001

struct point{
    double x, y;
    friend bool operator<(const point & p1, const point & p2){
        //if (p1.x==p2.x)return p1.y<p2.y;
        return p1.x<p2.x;
    }
} a[NMAX];
int n;
bool used[NMAX];
vector<int> st;
double cp(point p1, point p2, point p3){
    auto r=(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
    //cout<<"resp: "<<r<<endl;
    return r;
}
void conv(){
    st.push_back(1),
    st.push_back(2);
    used[2]=true;
    int p=1;
    for (int i=3; i>0; i+=(p=(i==n?-p:p))){
        if (used[i])continue;
        while (st.size()>=2 && cp(a[st[st.size()-2]], a[st[st.size()-1]], a[i])<0.0){
            used[st.back()]=false;
            //cout<<"in\n";
            st.pop_back();
        }
        //cout<<"out\n\n\n";
        st.push_back(i);
        used[i]=true;
    }
}
int main(){
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    cin>>n;
    for (int i=1; i<=n; ++i){
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1, a+n+1);
    conv();
    st.pop_back();
    cout<<st.size()<<endl;
    cout<<setprecision(6)<<fixed;
    for (auto it:st){
        cout<<a[it].x<<" "<<a[it].y<<"\n";
    }
    return 0;
}