Cod sursa(job #2700494)

Utilizator AlexNeaguAlexandru AlexNeagu Data 27 ianuarie 2021 21:23:40
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include<bits/stdc++.h>
// #define int long long
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pi;
const int mod = 1e9 + 7;
const int nax = 1e3 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

struct P {
    double x, y;
    void read() {
        in >> x >> y;
    }
    P operator -(const P &him) const {
        return P{x - him.x, y - him.y};
    }
    long long operator *(const P &him) const {
        return x * him.y - y * him.x;
    }
    void operator -=(const P &him) {
        x -= him.x;
        y -= him.y;
    }
    double triangle(const P &one, const P &two) const {
        return (one - *this) * (two - *this);
    }
    bool operator <(const P& him) const {
        return mp(x, y) < mp(him.x, him.y);
    }
};

vector<P> create(vector<P> points) {
    vector<P> hull;
    hull.push_back(points[0]);
    for(int i = 1; i < points.size(); ++i) {
        while((int) hull.size() >= 2) {
            P one = hull.end()[-1];
            P two = hull.end()[-2];
            if(two.triangle(one, points[i]) <= 0) {
                break;
            }
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }
    return hull;
}

int32_t main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    vector<P> points;
    int n;
    in >> n;
    for(int i = 1; i <= n; i++) {
        P x;
        x.read();
        points.pb(x);
    }

    sort(points.begin(), points.end());
    vector<P> upper = create(points);
    reverse(points.begin(), points.end());
    vector<P> bottom = create(points);

    upper.pop_back();
    bottom.pop_back();

    out << upper.size() + bottom.size() << '\n';
    
    out << fixed << setprecision(10);
    
    for(int i = 0; i < upper.size(); i++) {
        out << upper[i].x << ' ' << upper[i].y << '\n';
    } 
    for(int i = 0; i < bottom.size(); i++) {
        out << bottom[i].x << ' ' << bottom[i].y << '\n';
    } 
    return 0;
}