Cod sursa(job #1538288)

Utilizator zacuscaAlex Iordache zacusca Data 28 noiembrie 2015 19:11:46
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define Nmax 100010
#define inf 100000000000000.0

using namespace std;
int n, m;
double sol = inf;

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

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 A.x * B.y + B.x * C.y + C.x * A.y - A.x * C.y - B.x * A.y - 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++)
    {
        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(const punct &A, const punct &B)
{
    return sqrt ( (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y) );
}

inline double dist_line(const punct &A, const punct &B, double m)
{
    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();
    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;
        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;
}