Cod sursa(job #3325045)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 24 noiembrie 2025 16:14:45
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/extc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

struct Point {
    ld x;
    ld y;
};

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

vector<Point> hull(vector<Point> pts) {
    for (auto &p : pts) {
        if (p.x < pts[0].x || (p.x == pts[0].x && p.y < pts[0].y)) {
            swap(p, pts[0]);
        }
    }
    sort(pts.begin(), pts.end(), [&](Point a, Point b) {
        return det(pts[0], a, b) > 0;
    });
    
    vector<Point> stk;
    stk.push_back(pts[0]);
    stk.push_back(pts[1]);
    for (int i = 2; i < pts.size(); ++i) {
        while (stk.size() >= 2 && det(stk[stk.size() - 2], stk.back(), pts[i]) < 0) {
            stk.pop_back();
        }
        stk.push_back(pts[i]);
    }
    return stk;
}

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