Cod sursa(job #3141727)

Utilizator AndreiPaval03Andrei Paval AndreiPaval03 Data 15 iulie 2023 20:59:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.52 kb
#include <bits/stdc++.h>

using namespace std;

double product(
    std::pair<double, double> p0, 
    std::pair<double, double> p1, 
    std::pair<double, double> p2
) {
    return (p1.first - p0.first) * (p2.second - p0.second) - (p2.first - p0.first) * (p1.second - p0.second);
}

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

    int n; cin >> n;
    vector<pair<double, double>> points(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].first >> points[i].second;    
    }

    auto min_y_point = points[0];
    double max_y = points[0].second;
    for (int i = 1; i < n; ++i) {
        max_y = max(max_y, points[i].second);
        if (
            points[i].second < min_y_point.second
            || (
                points[i].second == min_y_point.second
                && points[i].first < min_y_point.first
            )
        ) {
            min_y_point = points[i];
        }
    }

    vector<pair<double, double>> left_chain;
    left_chain.push_back(min_y_point);
    while (left_chain.back().second < max_y) {
        auto last = left_chain.back();
        auto point = points[0];
        if (last == point) {
            point = points[1];
        }

        for (int i = 0; i < n; ++i) {
            if (points[i] == last) continue;
            
            double prod = product(last, points[i], point);
            if (prod < 0 || (prod == 0 && points[i].first < point.first)) {
                point = points[i];
            }
        }
        left_chain.push_back(point);
    }

    vector<pair<double, double>> right_chain;
    right_chain.push_back(min_y_point);
    while (right_chain.back().second < max_y) {
        auto last = right_chain.back();
        auto point = points[0];
        if (last == point) {
            point = points[1];
        }

        for (int i = 0; i < n; ++i) {
            if (points[i] == last) continue;

            double prod = product(last, points[i], point);
            if (prod > 0 || (prod == 0 && points[i].first > point.first)) {
                point = points[i];
            }
        }
        right_chain.push_back(point);
    }

    left_chain.pop_back();
    for (int i = left_chain.size() - 1; i >= 0; i--) {
        right_chain.push_back(left_chain[i]);
    }
    right_chain.pop_back();

    cout << right_chain.size() << endl;
    for (auto p : right_chain) {
        cout << setprecision(18) << p.first << " " << p.second << endl;
    }

    return 0;
}