Cod sursa(job #3310429)

Utilizator horatiu.avramAvram Popa Cristian Horatiu horatiu.avram Data 13 septembrie 2025 20:00:17
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include<bits/stdc++.h>
#define x first
#define y second
#define int long long
#define double long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<double,double>v[120022];
vector<pair<double,double>>res;
double det(double x1,double y1,double x2,double y2,double x3,double y3) {
    return x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1;
}
bool comp(pair<double,double>a,pair<double,double>b) {
    if(det(v[0].x,v[0].y,a.x,a.y,b.x,b.y)>0){
        return 1;
    }
    if(det(v[0].x,v[0].y,a.x,a.y,b.x,b.y)<0){
        return 0;
    }
    return a.x<b.x;
}
signed main() {
    int n;
    fin>>n;
    fin>>v[0].x>>v[0].y;
    for(int i=1; i<n; i++) {
        fin>>v[i].x>>v[i].y;
        if(v[i].x<v[0].x||(v[i].x==v[0].x&&v[i].y<v[0].y)) {
            swap(v[0],v[i]);
        }
    }
    v[n]=v[0];
    sort(v+1,v+n,comp);
    res.push_back(v[0]);
    for(int i=1; i<=n; i++) {
        bool gata=0;
        while(res.size()>=2&&!gata) {
            gata=1;
            pair<double,double>alf=res.back();
            res.pop_back();
            if(det(res.back().x,res.back().y,alf.x,alf.y,v[i].x,v[i].y)<=0) {
                gata=0;
            } else {
                res.push_back(alf);
            }
        }
        res.push_back(v[i]);
    }
    res.pop_back();
    fout<<res.size()<<endl;
    for(auto x:res) {
        fout<<setprecision(10)<<fixed<<x.x<<' '<<x.y<<'\n';
    }
    return 0;
}