Cod sursa(job #3357150)

Utilizator parus_majorParus Major parus_major Data 6 iunie 2026 17:45:00
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.53 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

struct Point {
    long long x, y;
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

// Produsele folosesc exclusiv long long pentru precizie exacta fara floating point
long long crossProduct(const Point& A, const Point& B, const Point& C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

long long dotProduct(const Point& A, const Point& B, const Point& C) {
    return (B.x - A.x) * (C.x - A.x) + (B.y - A.y) * (C.y - A.y);
}

// Invelisul Convex in O(N log N)
vector<Point> getConvexHull(vector<Point>& pts) {
    int n = pts.size();
    if (n <= 3) return pts;

    sort(pts.begin(), pts.end());
    vector<Point> hull;

    for (int i = 0; i < n; ++i) {
        while (hull.size() >= 2 && crossProduct(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(pts[i]);
    }

    size_t lower_size = hull.size();
    for (int i = n - 2; i >= 0; --i) {
        while (hull.size() > lower_size && crossProduct(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(pts[i]);
    }

    hull.pop_back();
    return hull;
}

int main() {
    // Fortam optimizarea fluxurilor I/O pentru rapiditate maxima
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ifstream fin("rubarba.in");
    ofstream fout("rubarba.out");

    int n;
    if (!(fin >> n)) return 0;

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

    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        return a.x == b.x && a.y == b.y;
        }), pts.end());

    vector<Point> hull = getConvexHull(pts);
    int h = hull.size();

    if (h <= 2) {
        fout << "0.00\n";
        return 0;
    }

    // Modificare fundamentala pentru 100p: arie stocata pe long double cu valoare maxima initiala uriasa
    long double min_area = 1e15;

    int top = 1, right = 1, left = 1;

    for (int i = 0; i < h; ++i) {
        Point A = hull[i];
        Point B = hull[(i + 1) % h];

        long long dx = B.x - A.x;
        long long dy = B.y - A.y;

        // Lungimea la patrat ramane long double pentru a asigura precizia impartirii ulterioare
        long double L2 = (long double)(dx * dx + dy * dy);

        while (crossProduct(A, B, hull[(top + 1) % h]) >= crossProduct(A, B, hull[top])) {
            top = (top + 1) % h;
        }

        while (dotProduct(A, B, hull[(right + 1) % h]) >= dotProduct(A, B, hull[right])) {
            right = (right + 1) % h;
        }

        if (i == 0) left = right;
        while (dotProduct(A, B, hull[(left + 1) % h]) <= dotProduct(A, B, hull[left])) {
            left = (left + 1) % h;
        }

        long long height_par = crossProduct(A, B, hull[top]);
        long long width_pro = dotProduct(A, B, hull[right]) - dotProduct(A, B, hull[left]);

        // Calculam aria intermediara folosind piese de tip long double
        long double current_area = ((long double)height_par * (long double)width_pro) / L2;

        if (current_area < min_area) {
            min_area = current_area;
        }
    }

    fout << fixed << setprecision(2) << min_area << "\n";

    return 0;
}