Cod sursa(job #3344905)

Utilizator dummy-accdummy acc dummy-acc Data 6 martie 2026 15:44:53
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

static char ibuf[1 << 18];
static int ipos, ilen;

static inline void refill() {
    ilen = fread(ibuf, 1, sizeof(ibuf), stdin);
    ipos = 0;
}

static inline int gc() {
    if (ipos == ilen) refill();
    return ibuf[ipos++];
}

static inline long long readll() {
    int c = gc();
    while (c <= ' ') c = gc();
    bool neg = false;
    if (c == '-') { neg = true; c = gc(); }
    long long v = 0;
    while (c >= '0') { v = v * 10 + (c - '0'); c = gc(); }
    return neg ? -v : v;
}

struct pt { long long x, y; };

static const int MAXN = 100001;
static pt p[MAXN], hull[2 * MAXN];
static int n, hsize;

static inline long long cross(pt a, pt b, pt c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

static inline long long dot(pt a, pt b, pt c) {
    return (b.x - a.x) * (c.x - a.x) + (b.y - a.y) * (c.y - a.y);
}

static inline long long dist2(pt a, pt b) {
    long long dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}

static bool cmp(const pt &a, const pt &b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

static void convex_hull() {
    std::sort(p, p + n, cmp);
    hsize = 0;
    for (int i = 0; i < n; i++) {
        while (hsize >= 2 && cross(hull[hsize - 2], hull[hsize - 1], p[i]) <= 0)
            --hsize;
        hull[hsize++] = p[i];
    }
    int lower = hsize;
    for (int i = n - 2; i >= 0; i--) {
        while (hsize > lower && cross(hull[hsize - 2], hull[hsize - 1], p[i]) <= 0)
            --hsize;
        hull[hsize++] = p[i];
    }
    --hsize;
}

static void solve() {
    int m = hsize;
    if (m <= 2) { fwrite("0.00\n", 1, 5, stdout); return; }

    double best = 1e18;
    int top = 1, right = 1, left;

    for (int i = 0; i < m; i++) {
        int ni = i + 1;
        if (ni == m) ni = 0;
        pt A = hull[i], B = hull[ni];
        long long len2 = dist2(A, B);

        for (;;) {
            int nt = top + 1;
            if (nt == m) nt = 0;
            if (std::abs(cross(A, B, hull[nt])) >= std::abs(cross(A, B, hull[top])))
                top = nt;
            else break;
        }

        for (;;) {
            int nr = right + 1;
            if (nr == m) nr = 0;
            if (dot(A, B, hull[nr]) >= dot(A, B, hull[right]))
                right = nr;
            else break;
        }

        if (i == 0) left = right;

        for (;;) {
            int nl = left + 1;
            if (nl == m) nl = 0;
            if (dot(A, B, hull[nl]) <= dot(A, B, hull[left]))
                left = nl;
            else break;
        }

        double h = std::abs((double)cross(A, B, hull[top]));
        double w = (double)(dot(A, B, hull[right]) - dot(A, B, hull[left]));
        double area = h * w / (double)len2;

        if (area < best) best = area;
    }

    printf("%.2f\n", best);
}

int main() {
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out", "w", stdout);

    n = (int)readll();
    for (int i = 0; i < n; i++) {
        p[i].x = readll();
        p[i].y = readll();
    }

    convex_hull();
    solve();
    return 0;
}