Cod sursa(job #3270971)

Utilizator razvan242Zoltan Razvan-Daniel razvan242 Data 24 ianuarie 2025 22:46:57
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <stack>
#include <vector>

using namespace std;

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

struct Point {
    long double x, y;
};

vector<Point> points;
int n;

void read() {
    fin >> n;

    long double x, y;
    for (int i = 1; i <= n; ++i) {
        fin >> x >> y;
        points.emplace_back(x, y);
    }
}

void selectLowestPoint() {
    int lowestPointIndex = 0;
    for (int i = 1; i < n; ++i) {
        if (points[i].x < points[lowestPointIndex].x || (points[i].x == points[lowestPointIndex].x && points[i].y < points[lowestPointIndex].y)) {
            lowestPointIndex = i;
        }
    }
    swap(points[0], points[lowestPointIndex]);
}

long double crossProduct(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

void sortPoints() {
    selectLowestPoint();
    sort(points.begin() + 1, points.end(), [](const Point& x, const Point& y) {
        return crossProduct(points[0], x, y) < 0;
    });
}

void convexHull() {
    vector<Point> stk;

    stk.push_back(points[0]);
    stk.push_back(points[1]);

    for (int i = 2; i < n; ++i) {
        while (stk.size() > 2 && crossProduct(stk[stk.size() - 2], stk[stk.size() - 1], points[i]) > 0) {
            stk.pop_back();
        }
        stk.push_back(points[i]);
    }
    reverse(stk.begin(), stk.end());
    fout << fixed;
    fout << stk.size() << '\n';
    for (const auto& p: stk) {
        fout << setprecision(12) << p.x << ' ' << p.y << '\n';
    }
}

int main() {
    read();
    sortPoints();
    convexHull();

    return 0;
}