Cod sursa(job #2740299)

Utilizator DragosC1Dragos DragosC1 Data 12 aprilie 2021 14:51:03
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
 
struct p {
    long double x, y;
    p operator- (p b) {
        return p{x - b.x, y - b.y};
    }
    void operator-= (p b) {
        x -= b.x;
        y -= b.y;
    }
    long double operator* (p b) {
        return 1LL * x * b.y - 1LL * y * b.x;
    }
    long double triangle (p b, p c) {
        return (b - *this) * (c - *this);
    }
};

int n;
vector<p> points;
vector<p> hull;

void read() {
    int i;
    ifstream f("infasuratoare.in");
    f >> n;
    points.resize(n);
    for (i = 1; i <= n; i++) 
        f >> points[i - 1].x >> points[i - 1].y;
}

bool csort(p a, p b) {
    if (a.x < b.x)
        return 1;
    else if (a.x == b.x && a.y < b.y)
        return 1;
    return 0;
}

void solve() {
    int i, size, times;
    p a, b;
    sort(points.begin(), points.end(), csort);
    for (times = 0; times < 2; times++) {
        size = hull.size();
        for (i = 0; i < n; i++) {
            while (hull.size() - size >= 2) {
                a = hull.end()[-2];
                b = hull.end()[-1];
                if (a.triangle(b, points[i]) <= 0)
                    break;
                hull.pop_back();
            }
            hull.emplace_back(points[i]);
        }
        hull.pop_back();
        reverse(points.begin(), points.end());
    }
}

void output() {
    ofstream g("infasuratoare.out");
    g << hull.size() << '\n';
    int i;
    for (i = hull.size() - 1; i >= 0; i--)
        g << setprecision(12) << fixed << hull[i].x << ' ' << hull[i].y << '\n';
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}