Cod sursa(job #2874481)

Utilizator AlexNeaguAlexandru AlexNeagu Data 19 martie 2022 14:45:59
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <bits/stdc++.h>
using namespace std;
#define int long long
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point {
    long double x, y;
    void read() {
        in >> x >> y;
    }
    void write() {
        out << fixed << setprecision(12) << x << ' ' << y << '\n';
    }
    point operator - (const point &B) const {
        return point{x - B.x, y - B.y};
    }
    void operator -= (const point &B) {
        x -= B.x;
        y -= B.y;
    }
    long double operator * (const point &B) const {
        return x * B.y - y * B.x;
    }
    long double orientation(const point &A, const point &B) const {
        return (A - *this) * (B - *this);
    }
    long double dist(point A) {
        A -= *this;
        return A.x * A.x + A.y * A.y;
    }
    bool operator <(const point &A) {
        if(x == A.x) {
            return y < A.y;
        }
        return x < A.x;
    }

};
vector<point> upperHull, lowerHull;

void add(bool upper, vector<point> &hull, point p) {
    while(hull.size() >= 2) {
        int sz = hull.size();
        point P1 = hull[sz - 2];
        point P2 = hull[sz - 1];
        int dir = P1.orientation(P2, p);
        if(dir < 0 == upper ) {
            break;
        }
        hull.pop_back();
    }
    hull.push_back(p);
}

int32_t main() {

    int n;
    in >> n;
    vector<point> points(n);
    for(int i = 0; i < n; ++i) {
        points[i].read();
    }

    sort(points.begin(), points.end());
    for(int i = 0; i < n; ++i) {
        add(true, upperHull, points[i]);
        add(false, lowerHull, points[i]);
    }

    reverse(upperHull.begin(), upperHull.end());
    upperHull.pop_back();
    lowerHull.pop_back();

    out << upperHull.size() + lowerHull.size() << '\n';

    for(auto it : lowerHull) {
        it.write();
    }
    for(auto it : upperHull) {
        it.write();
    }

}