Cod sursa(job #3268213)

Utilizator db_123Balaban David db_123 Data 13 ianuarie 2025 23:46:30
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct Info {
    double x;
    double y;
    int idx;
    Info() = default;
    Info(double x, double y) : x(x), y(y) {}
};

int n;
vector<Info> v;

void read() {
    cin >> n;
    v.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i].x >> v[i].y;
        v[i].idx = i;
    }
}

bool orientation(const Info &a1, const Info &a2, const Info &a3) {
   vector<vector<double>> mat(3, vector<double>(3));
   mat[0][0] = a1.x;
   mat[1][0] = a1.y;
   mat[2][0] = 1;

   mat[0][1] = a2.x;
   mat[1][1] = a2.y;
   mat[2][1] = 1;

   mat[0][2] = a3.x;
   mat[1][2] = a3.y;
   mat[2][2] = 1;

   return (mat[0][0] * mat[1][1] * mat[2][2]  +  mat[1][0] * mat[2][1] * mat[0][2]  +  mat[2][0] * mat[0][1] * mat[1][2]
        - mat[0][2] * mat[1][1] * mat[2][0]  -  mat[1][2] * mat[2][1] * mat[0][0]  -  mat[2][2] * mat[0][1] * mat[1][0])
   > 0;
}

void solve() {
    sort(v.begin() + 1, v.end(), [](const Info &a1, const Info &a2) -> bool {
        if (a1.y == a2.y) {
            return a1.x < a2.x;
        }
        return a1.y < a2.y;
    });

    Info pivot = v[1];
    sort(v.begin() + 2, v.end(), [&pivot](const Info &a1, const Info &a2) -> bool {
        return orientation(pivot, a1, a2);
    });
    
    vector<Info> hull;
    hull.emplace_back(v[1]);
    hull.emplace_back(v[2]);
    for (int i = 3; i < v.size(); i++) {
        while (hull.size() >= 2 && orientation(hull[hull.size() - 2], hull[hull.size() - 1], v[i]) == false) {
            hull.pop_back();
        }
        hull.emplace_back(v[i]);
    }
    cout << hull.size() << "\n";
    for (auto it : hull) {
        cout << fixed << setprecision(10) << it.x << " " << it.y << "\n";
    }
}

int main() {

    read();
    solve();
    return 0;
}