Cod sursa(job #3280157)

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

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

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

bool cmp(pct a,pct b){
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

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;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++){
        ///cout<<v[i].x<<" "<<v[i].y<<"\n";
        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--){
        ////cout<<v[i].x<<" "<<v[i].y<<"\n";
        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;
}