Cod sursa(job #3245861)

Utilizator StefannnnnStefan Stefannnnn Data 30 septembrie 2024 21:45:33
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <bits/stdc++.h>

using namespace std;

// Structura pentru a reprezenta un punct
struct Point {
    double x, y;

    // Comparator pentru sortarea punctelor dupa coordonata x si, in caz de egalitate, dupa coordonata y
    bool operator <(const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
};

// Functie care calculeaza produsul vectorial intre vectorii OA si OB
// Returneaza o valoare pozitiva daca fac viraj la stanga, negativa daca fac viraj la dreapta si 0 daca sunt coliniare
double cross(const Point& O, const Point& A, const Point& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

// Functie pentru a calcula infasuratoarea convexa folosind algoritmul lui Andrew
vector<Point> convexHull(vector<Point>& points) {
    int n = points.size();
    if (n < 3) return {};  // Daca avem mai putin de 3 puncte, nu putem forma un poligon

    // Sortam punctele dupa coordonata x (si dupa y daca x este egal)
    sort(points.begin(), points.end());

    // Vector pentru infasuratoarea convexa
    vector<Point> hull;

    // Construim partea de jos (lower hull)
    for (int i = 0; i < n; ++i) {
        while (hull.size() >= 2 && cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) <= 0)
            hull.pop_back();  // Eliminam punctul daca nu face viraj la stanga
        hull.push_back(points[i]);
    }

    // Construim partea de sus (upper hull)
    int lower_size = hull.size();
    for (int i = n-1; i >= 0; --i) {
        while (hull.size() > lower_size && cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) <= 0)
            hull.pop_back();
        hull.push_back(points[i]);
    }

    // Eliminam ultimul punct deoarece este egal cu primul (inchidem poligonul)
    hull.pop_back();

    return hull;
}

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

    int N;
    cin >> N;

    vector<Point> points(N);
    for (int i = 0; i < N; ++i) {
        fin >> points[i].x >> points[i].y;
    }

    // Calculam infasuratoarea convexa
    vector<Point> hull = convexHull(points);

    // Scriem rezultatul
    fout << hull.size() << '\n';
    fout << fixed << setprecision(6);
    for (const Point& p : hull) {
        fout << p.x << " " << p.y << '\n';
    }

    return 0;
}