Cod sursa(job #3233249)

Utilizator MirceaDonciuLicentaLicenta Mircea Donciu MirceaDonciuLicenta Data 2 iunie 2024 20:46:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

struct Point {
    double x, y;
};

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);
}

bool compare(const Point &A, const Point &B) {
    if (A.x != B.x)
        return A.x < B.x;
    return A.y < B.y;
}

vector<Point> convexHull(vector<Point> &points) {
    int n = points.size(), k = 0;
    if (n <= 3) return points;
    vector<Point> H(2 * n);

    sort(points.begin(), points.end(), compare);

    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(H[k - 2], H[k - 1], points[i]) <= 0) k--;
        H[k++] = points[i];
    }

    for (int i = n - 2, t = k + 1; i >= 0; --i) {
        while (k >= t && cross(H[k - 2], H[k - 1], points[i]) <= 0) k--;
        H[k++] = points[i];
    }

    H.resize(k - 1);
    return H;
}

int main() {
    ifstream infile("infasuratoare.in");
    ofstream outfile("infasuratoare.out");

    int N;
    infile >> N;
    vector<Point> points(N);

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

    vector<Point> hull = convexHull(points);

    outfile << hull.size() << endl;
    for (const auto &point : hull) {
        outfile << fixed << setprecision(12) << point.x << " " << point.y << endl;
    }

    infile.close();
    outfile.close();

    return 0;
}