Cod sursa(job #2978107)

Utilizator HandoMihnea-Vicentiu Hando Data 12 februarie 2023 23:20:48
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.16 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ar array
#define vt vector
#define pq priority_queue
#define pu push
#define pub push_back
#define em emplace
#define emb emplace_back

#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allp(x, l, r) x.begin() + l, x.begin() + r
#define len(x) (int)x.size()

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

void set_fixed(int p = 0) {
    cout << fixed << setprecision(p);
}

void set_scientific() {
    cout << scientific;
}

template <class T, size_t N>
void re(array <T, N>& x);
template <class T> 
void re(vt <T>& x);

template <class T> 
void re(T& x) {
    cin >> x;
}

template <class T, class... M> 
void re(T& x, M&... args) {
    re(x); re(args...);
}

template <class T> 
void re(vt <T>& x) {
    for(auto& it : x)
        re(it);
}

template <class T, size_t N>
void re(array <T, N>& x) {
    for(auto& it : x)
        re(it);
}

template <class T, size_t N>
void wr(array <T, N> x);
template <class T> 
void wr(vt <T> x);

template <class T> 
void wr(T x) {
    cout << x;
}

template <class T, class ...M>  void wr(T x, M... args) {
    wr(x), wr(args...);
}

template <class T> 
void wr(vt <T> x) {
    for(auto it : x)
        wr(it, ' ');
}

template <class T, size_t N>
void wr(array <T, N> x) {
    for(auto it : x)
        wr(it, ' ');
}


inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

struct PT {
    double x, y;
    PT() {
        x = y = 0;
    }

    PT(double x, double y) : x(x), y(y) {}
    PT(const PT& p) : x(p.x), y(p.y) {}
    PT operator + (const PT& a) const {
        return PT(x + a.x, y + a.y);
    }
    PT operator - (const PT& a) const {
        return PT(x - a.x, y - a.y);
    }
    PT operator * (const double a) const {
        return PT(x * a, y * a);
    }

    friend istream& operator>> (istream &stream, PT& a){
        stream >> a.x >> a.y;
        return stream;
    }
};

inline double dot(PT a, PT b) { 
    return a.x * b.x + a.y * b.y; 
}

inline double dist2(PT a, PT b) { 
    return dot(a - b, a - b); 
}

inline double cross(PT a, PT b) { 
    return a.x * b.y - a.y * b.x; 
}

int orientation(PT a, PT b, PT c) {
    double v = cross(b - a, c - a);
    if (v < 0) return -1; //clockwise
    if (v > 0) return +1; // counter-clockwise
    return 0;
}

bool cw(PT a, PT b, PT c, bool include_collinear = false) {
    int o = orientation(a, b, c);
    return o < 0 || (include_collinear and o == 0);
}

bool collinear(PT a, PT b, PT c) { 
    return orientation(a, b, c) == 0; 
}

void convex_hull(vt <PT>& a, bool include_collinear = false) {
    // select the point with the lowest Y coord.
    PT p0 = *min_element(a.begin(), a.end(), [](PT a, PT b) {
        return make_pair(a.y, a.x) < make_pair(b.y, b.x);
    });

    /*sort the points by the angle relative to the bottom most
      point and the horizontal
    */
    sort(all(a), [&p0](const PT& a, const PT& b) {
        int o = orientation(p0, a, b);
        if (o == 0)
            return dist2(p0, a) < dist2(p0, b);
        return o < 0;
    });

    /* If you need to include the collinear points while doing a Graham scan, you need another step after sorting. 
    You need to get the points that have the biggest polar distance from P0 (these should be at the end of the sorted vector) and are collinear. 
    The points in this line should be reversed so that we can output all the collinear points, otherwise the algorithm would get the nearest point in this line and bail.
    This step shouldn't be included in the non-collinear version of the algorithm, otherwise you wouldn't get the smallest convex hull.
    */
    if (include_collinear) {
        int i = len(a) - 1;
        while (i >= 0 and collinear(p0, a[i], a.back())) i--;
        reverse(a.begin() + i + 1, a.end());
    }

    /* We iterate through each point one by one, 
    and make sure that the current point and the two before it make a clockwise turn, 
    otherwise the previous point is discarded, since it would make a non-convex shape. 
    Checking for clockwise or anticlockwise nature can be done by checking the orientation.
    */
    vt <PT> st;
    for (int i = 0; i < len(a); ++i) {
        while (len(st) > 1 && !cw(st[len(st) - 2], st.back(), a[i], include_collinear)) {
            st.pop_back();
        }
        st.pub(a[i]);
    }

    a = st;
}

void solve() {
    int n; re(n);
    vt <PT> v(n); re(v);
    convex_hull(v, false);


    wr(len(v), '\n');
    set_fixed(12);
    for (int i = 0; i < len(v); ++i) {
        wr(v[!i? i : len(v) - i].x, ' ', v[!i? i : len(v) - i].y, '\n');
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    Open("infasuratoare");

    int t = 1;
    for(;t;t--) {
        solve();
    }
    
    return 0;
}