Cod sursa(job #3351869)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 21 aprilie 2026 21:11:58
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back

struct Point {
    long double x, y;
};

bool operator == (Point a, Point b) {
    return a.x == b.x && a.y == b.y;
}

double det(Point a, Point b, Point c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

vector<Point> HullHalf(vector<Point> pts, int z) {
    vector<Point> stk;
    for (auto p : pts) {
        while (stk.size() >= 2 && z * det(stk[stk.size() - 2], stk.back(), p) < 0) stk.pop_back();
        stk.push_back(p);
    }
    return stk;
}

vector<Point> convexhull(vector<Point> pts) {
    sort(pts.begin(), pts.end(), [&](Point a, Point b) { return a.x < b.x || (a.x == b.x && a.y < b.y); });
    pts.resize(unique(pts.begin(), pts.end()) - pts.begin());
    vector<Point> up = HullHalf(pts, +1), low = HullHalf(pts, -1); 
    up.insert(up.end(), low.rbegin() + 1, low.rend() - 1);
    return up;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    cout << setprecision(10) << fixed;
    int n; cin >> n;
    vector<Point> pts(n);
    for (auto &x : pts) cin >> x.x >> x.y;
    auto ch = convexhull(pts);
    cout << ch.size() << "\n";
    for (auto [x, y] : ch) {
        cout << x << " " << y << "\n";
    }
    return 0;
}