Cod sursa(job #3296035)

Utilizator radiantstorkAmadeus L radiantstork Data 10 mai 2025 21:00:40
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

std::pair<double, double> pivot;

void read_input(std::vector<std::pair<double, double> > &points, int &point_count) {
    std::ifstream f("infasuratoare.in");
    f >> point_count;
    for (int i = 0; i < point_count; ++i) {
        std::pair<double, double> p;
        f >> p.first >> p.second;
        points.push_back(p);
    }
    f.close();
}

double squared_distance(const std::pair<double, double> &p1, const std::pair<double, double> &p2) {
    return (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second);
}

int orientation(const std::pair<double, double> &p1, const std::pair<double, double> &p2,
                const std::pair<double, double> &p3) {
    const double x = (p2.second - p1.second) * (p3.first - p1.first) - (p3.second - p1.second) * (p2.first - p1.first);
    if (x == 0) return 0;
    return (x > 0) ? 1 : -1; // 1=sens_trigonometric, -1=sens_orar
}

bool polar_angle_cmp(const std::pair<double, double> &a, const std::pair<double, double> &b) {
    const int o = orientation(pivot, a, b);
    if (o == 0) {
        return squared_distance(pivot, a) < squared_distance(pivot, b);
    }
    return o == 1;
}

void grahams_scan(std::vector<std::pair<double, double> > &points, const int point_count) {
    if (point_count < 3) {
        return;
    }

    pivot = *std::ranges::min_element(
        points, [](const std::pair<double, double> &a, const std::pair<double, double> &b) {
            return (a.second < b.second) || (a.second == b.second && a.first < b.first);
        });

    std::ranges::sort(points, polar_angle_cmp);

    std::vector<std::pair<double, double> > hull;
    hull.push_back(points[0]);
    hull.push_back(points[1]);
    for (int i = 2; i < point_count; ++i) {
        while (hull.size() >= 2 && orientation(hull[hull.size() - 2], hull.back(), points[i]) != 1) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }

    std::ofstream g("infasuratoare.out");
    g << hull.size() << "\n";
    for (const auto &[x, y]: hull) {
        g << x << " " << y << "\n";
    }
    g.close();
}

int main() {
    std::vector<std::pair<double, double> > points;
    int point_count;

    read_input(points, point_count);
    grahams_scan(points, point_count);
    return 0;
}