Cod sursa(job #3295993)

Utilizator radiantstorkAmadeus L radiantstork Data 10 mai 2025 16:19:03
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>

void read_input(std::vector<std::pair<double, double> > &points, int &point_count) {
    std::ifstream f("infasuratoare.in");
    f >> point_count;
    points.resize(point_count);

    for (int i = 0; i < point_count; i++) {
        f >> points[i].first >> points[i].second;
    }

    // for (const auto &[x, y]: points) {
    //     std::cout << x << ' ' << y << '\n';
    // }

    f.close();
}

double orientation(std::pair<double, double>& a, std::pair<double, double>& b, std::pair<double, double>& c) {
    return (b.second - a.second) * (c.first - a.first) - (c.second - a.second) * (b.first - a.first);
}

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

    auto leftmost_index = 0;
    for (int i = 1; i < point_count; ++i) {
        if (points[i].first < points[leftmost_index].first) {
            leftmost_index = i;
        }
    }

    int current = leftmost_index;
    std::vector<std::pair<double, double> > hull;

    do {
        hull.push_back(points[current]);

        int next = (current + 1) % point_count;
        for (int i = 0; i < point_count; ++i) {
            if (i == current) continue;

            double x = orientation(points[current], points[next], points[i]);
            if (x < 0) {
                next = i;
            }
        }

        current = next;
    } while (current != leftmost_index);

    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);
    jarvis_march(points, point_count);
    return 0;
}