Cod sursa(job #3280153)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 25 februarie 2025 17:34:57
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;

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

struct pct{
    long double x,y;
} v[120001];
deque<pct> q;

bool det(pct a,pct b,pct c){
    return (((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x))<0);
}

int main()
{
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;
    }
    for(i=1;i<=n;i++){
        while(q.size()>1 && det(q[q.size()-2],q.back(),v[i])) q.pop_back();
        q.push_back(v[i]);
    }
    for(i=n-1;i>=1;i--){
        while(q.size()>1 && det(q[q.size()-2],q.back(),v[i])) q.pop_back();
        q.push_back(v[i]);
    }
    cout<<q.size()-1<<"\n";
    for(i=0;i<q.size()-1;i++){
        cout<<fixed<<setprecision(12)<<q[i].x<<" "<<q[i].y<<"\n";
    }
    return 0;
}