Cod sursa(job #3148057)

Utilizator andiRTanasescu Andrei-Rares andiR Data 29 august 2023 03:34:39
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <algorithm>

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;
};
ll distsq(point a, point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
ll 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);
    if (d!=0)
        return d>0;
    return distsq({0, 0}, a)>distsq({0, 0}, b);
}
//             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
    ll i=2;
    while (det(v[0], v[1], v[i])==0)
        i++;
    reverse(v+1, v+i); ///reverse the first elements of the convex hull that are colinear with O(0, 0)
    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;
    }
    for (ll i=0; i<m; i++){
        sol[i].x+=mnx;
        sol[i].y+=mny;
    }
    m=k;
}

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<<m<<'\n';
    for (int i=0; i<m; i++)
        fout<<sol[i].x<<' '<<sol[i].y<<'\n';
    return 0;
}