Cod sursa(job #1295679)

Utilizator RaduVisanRadu Visan RaduVisan Data 19 decembrie 2014 23:29:00
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;

const int NMAX = 100010;

int N, K, Next[NMAX], Top;
pair<int, int> V[NMAX], Hull[NMAX], Stack[NMAX];
double Ans;

long long Det(pair<int, int> A, pair<int, int> B, pair<int, int> C)
{
    return 1LL * A.first * (B.second - C.second) + 1LL * B.first * (C.second - A.second) + 1LL * C.first * (A.second - B.second);
}

void Add()
{
    Top = 0;
    Stack[Top ++] = V[1];
    Stack[Top ++] = V[2];
    for(int i = 3; i <= N; ++ i)
    {
        while(Top >= 2 && Det(Stack[Top - 2], Stack[Top - 1], V[i]) <= 0LL) Top --;
        Stack[Top ++] = V[i];
    }

    for(int i = 0; i < Top - 1; ++ i)
        Hull[++ K] = Stack[i];
}

void ConvexHull()
{
    sort(V + 1, V + N + 1);
    Add();
    reverse(V + 1, V + N + 1);
    Add();
}

long long CrossProduct(pair<int, int> A, pair<int, int> B)
{
    return 1LL * A.first * B.second - 1LL * A.second * B.first;
}

long long DotProduct(pair<int, int> A, pair<int, int> B)
{
    return 1LL * A.first * B.first + 1LL * A.second * B.second;
}

pair<int, int> Translate(pair<int, int> A, pair<int, int> B)
{
    return make_pair(B.first - A.first, B.second - A.second);
}

double Dist(pair<int, int> A, pair<int, int> B, double Slope)
{
    return fabs((1.0 * A.second - A.first * Slope) - (1.0 * B.second - B.first * Slope)) / sqrt(Slope * Slope + 1);
}

void RotatingCalipers()
{
    for(int i = 1; i <= K; ++ i)
        Next[i] = (i + 1 <= K ? i + 1 : 1);

    int i, j = 1, k, l;
    double DistX, DistY;
    for(i = 1; i <= K; ++ i)
    {
        while(DotProduct( Translate(Hull[i], Hull[Next[i]]), Translate(Hull[j], Hull[Next[j]])) > 0LL) j = Next[j];
        if(i == 1) k = j;

        while(CrossProduct( Translate(Hull[i], Hull[Next[i]]), Translate(Hull[k], Hull[Next[k]])) > 0LL) k = Next[k];
        if(i == 1) l = k;

        while(DotProduct( Translate(Hull[i], Hull[Next[i]]), Translate(Hull[l], Hull[Next[l]])) < 0LL) l = Next[l];

        if(Hull[i].first == Hull[Next[i]].first)
        {
            DistX = fabs(Hull[k].first - Hull[i].first);
            DistY = fabs(Hull[j].second - Hull[l].second);
        }else if(Hull[i].second == Hull[Next[i]].second)
        {
            DistX = fabs(Hull[j].first - Hull[l].first);
            DistY = fabs(Hull[k].second - Hull[i].second);
        }else
        {
            double Slope = 1.0 * (Hull[Next[i]].second - Hull[i].second) / (Hull[Next[i]].first - Hull[i].first);
            DistX = Dist(Hull[i], Hull[k], Slope);
            DistY = Dist(Hull[j], Hull[l], -1.0 / Slope);
        }

        if(i == 1) Ans = DistX * DistY;
        else if(DistX * DistY < Ans) Ans = DistX * DistY;
    }
}

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

    scanf("%i", &N);
    for(int i = 1; i <= N; ++ i)
        scanf("%i %i", &V[i].first, &V[i].second);

    if(N >= 2)
        ConvexHull(), RotatingCalipers();

    printf("%.3f\n", Ans);
}