Cod sursa(job #3305766)

Utilizator stefan1010Stefan Bogdan stefan1010 Data 4 august 2025 19:52:20
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
///Infoarena "Infasuratoare convexa"
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMAX 120010
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,st[NMAX],k;
struct punct
{
    double x,y;
}v[NMAX];

double cross_product(const punct& A,const  punct& B,const  punct& C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

inline int cmp(const punct& a,const punct& b)
{
    double cp = cross_product(v[1], a, b);
    if (cp == 0) {
        double distA = (a.x - v[1].x) * (a.x - v[1].x) + (a.y - v[1].y) * (a.y - v[1].y);
        double distB = (b.x - v[1].x) * (b.x - v[1].x) + (b.y - v[1].y) * (b.y - v[1].y);
        return distA < distB;
    }
    return cp > 0;
}

void sortare() {
    int pos = 1;
    for (int i = 2; i <= n; ++i)
        if (v[i].x < v[pos].x || (v[i].x == v[pos].x  &&  v[i].y < v[pos].y))
            pos = i;
    swap(v[1], v[pos]);
    sort(v + 2, v + n + 1, cmp);
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
    sortare();
    st[1] = 1;
    st[2] = 2;
    k = 2;
    for (int i = 3; i <= n; ++i) {
        while (k >= 2 && cross_product(v[st[k - 1]], v[st[k]], v[i]) <= 0)
            --k;
        st[++k] = i;
    }

    fout<<fixed;
    fout<<k<<'\n';
    for(int i=1;i<=k;i++)
    {
        fout<<setprecision(12)<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
    }
    return 0;
}