Cod sursa(job #3309650)

Utilizator InformaticianInDevenire1Munteanu Mihnea Gabriel InformaticianInDevenire1 Data 7 septembrie 2025 13:35:12
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 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[120021];
vector <pair <double,double>> ans;

double Determinant(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 (Determinant(v[0].x,v[0].y,a.x,a.y,b.x,b.y)>0) return 1;
    if (Determinant(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 or (v[i].x==v[0].x and v[i].y<v[0].y)) swap(v[0],v[i]);
    }
    v[n] = v[0];
    sort(v+1,v+n,Comp);
    ans.push_back(v[0]);
    for (int i=1;i<=n;++i){
        bool loob = 1;
        while (ans.size()>=2 and loob){
            loob = 0;
            pair <double,double> alfa = ans.back();
            ans.pop_back();
            if (Determinant(ans.back().x,ans.back().y,alfa.x,alfa.y,v[i].x,v[i].y)<=0) loob = 1;
            else ans.push_back(alfa);
        }
        ans.push_back(v[i]);
    }
    ans.pop_back();
    fout << ans.size() << '\n';
    for (auto x:ans){
        fout << setprecision(8) << fixed << x.x << ' ' << x.y << '\n';
    }
    return 0;
}