Cod sursa(job #3309271)

Utilizator iustinola16Olariu Iustin iustinola16 Data 3 septembrie 2025 11:29:30
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int NMAX = 120005;
const long double EPS = 1e-12;

struct Point {
    long double x, y;
};

long double cp(Point A, Point B, Point C) {
    return (B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x);
}

bool cmp(Point &A, Point &B) {
    return A.x < B.x || (A.x == B.x && A.y < B.y);
}

int N;
Point v[NMAX];

int main() {
    fin >> N;
    for (int i = 0; i < N; i++) {
        fin >> v[i].x >> v[i].y;
    }

    sort(v, v + N, cmp);

    vector<Point> upper_hull;
    upper_hull.push_back(v[0]);
    upper_hull.push_back(v[1]);
    for (int i = 2; i < N; i++) {
        while (upper_hull.size() >= 2 && cp(upper_hull[upper_hull.size() - 2], upper_hull[upper_hull.size() - 1], v[i]) < EPS) {
            upper_hull.pop_back();
        }
        upper_hull.push_back(v[i]);
    }

    vector<Point> lower_hull;
    lower_hull.push_back(v[N - 1]);
    lower_hull.push_back(v[N - 2]);
    for (int i = N - 3; i >= 0; i--) {
        while (lower_hull.size() >= 2 && cp(lower_hull[lower_hull.size() - 2], lower_hull[lower_hull.size() - 1], v[i]) < EPS) {
            lower_hull.pop_back();
        }
        lower_hull.push_back(v[i]);
    }

    reverse(lower_hull.begin(), lower_hull.end());
    reverse(upper_hull.begin(), upper_hull.end());
    lower_hull.pop_back();
    upper_hull.pop_back();

    vector<Point> hull = lower_hull;
    hull.insert(hull.end(), upper_hull.begin(), upper_hull.end());

    fout << hull.size() << '\n';
    fout << fixed;
    for (int i = 0; i < hull.size(); i++) {
        fout << setprecision(12) << hull[i].x << ' ' << hull[i].y << '\n';
    }
    return 0;
}