Cod sursa(job #3148061)

Utilizator andiRTanasescu Andrei-Rares andiR Data 29 august 2023 04:44:35
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
typedef long long ll;
const ll Nmax=1e5+20005, inf=1e9+5;
struct point{
    double x, y;
};
double distsq(point a, point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
double det(point a, point b, point c){
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmpCH(point a, point b){
    ll d=det({0, 0}, a, b);
    return d>0;
}
//             vector / size of v / solution / size of sol
void convex_hull(point v[], ll n, point sol[], ll &m){ ///we take as many points
    /// Graham scan from down-left most point
    double mny=inf, mnx=inf;
    for (ll i=0; i<n; i++)
        if (v[i].y<mny){
            mny=v[i].y;
            mnx=v[i].x;
        }
        else if (v[i].y==mny && v[i].x<mnx)
            mnx=v[i].x;
    for (ll i=0; i<n; i++){///translation
            v[i].x-=mnx;
            v[i].y-=mny;
        if (v[i].x==0 && v[i].y==0)
            swap(v[i], v[0]);
    }
    sort (v+1, v+n, cmpCH); ///sort in order of the angle
    sol[0].x=v[0].x; sol[0].y=v[0].y;
    sol[1].x=v[1].x; sol[1].y=v[1].y;
    ll k=2;
    for (ll i=2; i<n; i++){
        while (det(sol[k-2], sol[k-1], v[i])<0)
            k--;
        sol[k].x=v[i].x;
        sol[k].y=v[i].y;
        k++;
    }
    m=k;
    for (ll i=0; i<m; i++){
            sol[i].x+=mnx;
            sol[i].y+=mny;
    }
}

ll n;
point v[Nmax], sol[Nmax];
int main()
{

    fin>>n;
    for (int i=0; i<n; i++)
        fin>>v[i].x>>v[i].y;
    ll m=0;
    convex_hull(v, n, sol, m);
    fout<<fixed<<m<<'\n';
    for (int i=0; i<m; i++)
        fout<<setprecision(12)<<sol[i].x<<' '<<sol[i].y<<'\n';
    return 0;
}