Cod sursa(job #3148054)

Utilizator andiRTanasescu Andrei-Rares andiR Data 29 august 2023 03:27:02
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.72 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>

#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
typedef long long ll;
const ll Nmax=1e2+5, inf=1e9+5;
using pll=pair<ll, ll>;
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 dist(point a, point b){
    return sqrt((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);
}
double pant(point a, point b){
    if (a.x==b.x)
        return -inf;
    return (a.y-b.y)/(a.x-b.x);
}
double trarea(point a, point b, point c){
    ll d=det(a, b, c);
    if (d%2==0)
        return d/2;
    if (d>0)
        return d/2+0.5;
    return d/2-0.5;
}
void ecdr(point A, point B, ll &a, ll &b, ll&c){
    a=A.y-B.y;
    b=B.x-A.x;
    c=A.x*(B.y-A.y)-A.y*(B.x-A.x);
}
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;
}

int n;
point v[Nmax], sol[Nmax];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    int mny=inf, mnx=inf;
    for (int i=0; i<n; i++)
        cin>>v[i].x>>v[i].y;
    ll m;
    convex_hull(v, n, sol, m);
    cout<<m<<'\n';
    for (int i=0; i<m; i++)
        cout<<sol[i].x<<' '<<sol[i].y<<'\n';
    return 0;
}