Cod sursa(job #1538276)

Utilizator zacuscaAlex Iordache zacusca Data 28 noiembrie 2015 18:58:04
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.38 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define MAX_N 100010

#define inf 100000000000000.0
#define VMAX 1000000

int n, m;

double sol = inf;

struct punct {
    double x, y;
} A[MAX_N], Hull[MAX_N];

inline bool cmp(const punct &P, const punct &Q) {
    return atan2(P.y - A[1].y, P.x - A[1].x) < atan2(Q.y - A[1].y, Q.x - A[1].x);
}

inline double det(const punct &A, const punct &B, const punct &C) {
    return 1LL * A.x * B.y + 1LL * B.x * C.y + 1LL * C.x * A.y -
           1LL * A.x * C.y - 1LL * B.x * A.y - 1LL * C.x * B.y;
}

void get_hull() {
    int p = 1;

    for (int i = 2; i <= n; i++)
        if (A[i].x < A[p].x || (A[i].x == A[p].x && A[i].y < A[p].y))
            p = i;

    swap(A[1], A[p]);

    sort(A + 2, A + n + 1, cmp);

    Hull[1] = A[1]; Hull[2] = A[2]; m = 2;
    for (int i = 3; i <= n; i++) {
        //verific daca punctul curent este pe ultima latura a infasuratorii
        if (!(det(A[i], Hull[m], Hull[m - 1]) == 0 && min(Hull[m].x, Hull[m - 1].x) <= A[i].x && A[i].x <= max(Hull[m].x, Hull[m - 1].x)))
            Hull[++m] = A[i];

        while (m > 2 && det(Hull[m - 2], Hull[m - 1], Hull[m]) <= 0) {
            swap(Hull[m - 1], Hull[m]);
            m--;
        }
    }

    n = m;
    for (int i = 1; i <= n; i++)
        A[i] = Hull[i];
}

inline double dist(punct A, punct B) {
    double ans = (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);

    return sqrt(ans);
}

inline double dist_line(punct A, punct B, double m) { //dreapta fata de care trebuie sa gasesc distanta are tangenta m si trece prin B
    //cazuri speciale: m = 0 sau m = inf

    if (m == 0)
        return fabs(A.y - B.y);

    if (m == inf)
        return fabs(A.x - B.x);

    double n = B.y - m * B.x;

    punct C;
    C.x = B.x + 1;
    C.y = C.x * m + n;

    double h = det(A, B, C) / dist(B, C);
    if (h < 0)
        h = -h;

    return h;
}

inline int next(int i) {
    return (i < n) ? (i + 1) : 1;
}

inline double inv(double m) {
    if (m == 0)
        return inf;
    if (m == inf)
        return 0;

    return -1.0 / m;
}

void solve() {
    get_hull();

    //algoritm O(n^2)

    for (int i = 1; i <= n; i++) {
        int nxt = next(i);

        double m;
        if (A[i].x == A[nxt].x)
            m = inf;
        else
            m = 1.0 * (A[nxt].y - A[i].y) / (A[nxt].x - A[i].x);

        int left = i, up = i, right = i;

        //gasesc up si left
        for (int j = next(i); j != i; j = next(j)) {
            if (dist_line(A[j], A[i], m) > dist_line(A[up], A[i], m))
                up = j;
            if (dist_line(A[j], A[i], inv(m)) > dist_line(A[left], A[i], inv(m)))
                left = j;
        }

        for (int j = next(left); j != left; j = next(j))
            if (dist_line(A[j], A[left], inv(m)) > dist_line(A[right], A[left], inv(m)))
                right = j;

        double current_sol = dist_line(A[up], A[i], m) * dist_line(A[left], A[right], inv(m));
        if (current_sol < sol)
            sol = current_sol;
    }

    printf("%.2lf\n", sol);
}

int main() {

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

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf %lf", &A[i].x, &A[i].y);

    solve();

    return 0;
}