Cod sursa(job #3346323)

Utilizator RazvanVelcuVelcu Razvan RazvanVelcu Data 13 martie 2026 10:56:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
};

double cross(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

int main() {
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");

    int n;
    cin >> n;

    vector<Point> p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i].x >> p[i].y;

    sort(p.begin(), p.end(), [](Point a, Point b) {
        if (a.x == b.x) return a.y < b.y;
        return a.x < b.x;
    });

    vector<Point> hull;

    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 &&
               cross(hull[hull.size()-2], hull[hull.size()-1], p[i]) <= 0)
            hull.pop_back();
        hull.push_back(p[i]);
    }

    int t = hull.size() + 1;

    for (int i = n-2; i >= 0; i--) {
        while (hull.size() >= t &&
               cross(hull[hull.size()-2], hull[hull.size()-1], p[i]) <= 0)
            hull.pop_back();
        hull.push_back(p[i]);
    }

    hull.pop_back();

    cout << hull.size() << "\n";
    cout << fixed << setprecision(6);

    for (auto &pt : hull)
        cout << pt.x << " " << pt.y << "\n";

    return 0;
}