Cod sursa(job #2740294)

Utilizator DragosC1Dragos DragosC1 Data 12 aprilie 2021 14:41:50
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 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 (x * b.y - 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;
    return 0;
}

void solve() {
    int i, S;
    p a, b;
    sort(points.begin(), points.end(), csort);
    for (i = 1; i <= 2; i++) {
        S = hull.size();
        for (p c : points) {
            while (hull.size() - S > 2) {
                a = hull.end()[-2];
                b = hull.end()[-1];
                if (a.triangle(b, c) < 0) 
                    break;
                hull.pop_back();
            }
            hull.push_back(c);
        }
        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;
}