Cod sursa(job #920063)

Utilizator visanrVisan Radu visanr Data 20 martie 2013 00:01:42
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.4 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

#define LL long long
#define PI pair<int, int>
#define x first
#define y second
#define Nmax 100010

PI V[Nmax], Convex[Nmax], Stack[Nmax];
int N, K, StackSize;
double Xdist, Ydist, Ans;

int Det(PI A, PI B, PI C)
{
    return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}

void Add_Points_To_Convex_Hull()
{
    StackSize = 0;
    Stack[StackSize++] = V[1];
    Stack[StackSize++] = V[2];
    for(int i = 3; i <= N; ++ i)
    {
        while(StackSize >= 2 && Det(Stack[StackSize - 2], Stack[StackSize - 1], V[i]) < 0) StackSize --;
        Stack[StackSize++] = V[i];
    }
    for(int i = 1; i < StackSize; ++ i) Convex[++K] = Stack[i];
}

void Do_Convex_Hull()
{
    sort(V + 1, V + N + 1);
    Add_Points_To_Convex_Hull();
    reverse(V + 1, V + N + 1);
    Add_Points_To_Convex_Hull();
}

//A * B = |A| * |B| * sin (unghiul dintre ele)

LL CrossProduct(PI A, PI B) { return (1LL * A.x * B.y - 1LL * A.y * B.x); }

//A * B = |A| * |B| * cos (unghiul dintre ele)

LL DotProduct(PI A, PI B) { return (1LL * A.x * B.x + 1LL * A.y * B.y); };

int Next(int Pos) { return (Pos == K ? 1 : Pos + 1); }

//Translatez segmentul in origine

PI Translate(PI A, PI B) { return make_pair(B.x - A.x, B.y - A.y); }

//Distanta dintre 2 drepte paralele este (B2 - B1) / sqrt(panta * panta + 1)
//Unde Y1 = panta * X1 + B1, analog B2

double GetDist(PI A, PI B, double Slope)
{
    return fabs((1.0 * A.y - Slope * A.x) - (1.0 * (B.y - Slope * B.x))) / sqrt(Slope * Slope + 1.0);
}

void GetArea()
{
    int i, j = 1, k, m;
    for(i = 1; i <= K; ++ i)
    {
        //Daca DotProduct e > 0, inseamna ca cos(unghi) e > 0, adica unghiul este < 90

        while(DotProduct(Translate(Convex[i], Convex[Next(i)]), Translate(Convex[j], Convex[Next(j)])) > 0) j = Next(j);
        if(i == 1) k = j;

        //Daca CrossProduct e > 0, inseamna ca sin (unghi) > 0, adica unghiul e intre 0 si 180

        while(CrossProduct(Translate(Convex[i], Convex[Next(i)]), Translate(Convex[k], Convex[Next(k)])) > 0) k = Next(k);
        if(i == 1) m = k;

        //Daca DotProduct este < 0, inseamna ca cos (unghi) e < 0, adica unghiul este intre 90 si 270 de grade

        while(DotProduct(Translate(Convex[i], Convex[Next(i)]), Translate(Convex[m], Convex[Next(m)])) < 0) m = Next(m);
        if(Convex[i].x == Convex[Next(i)].x)
        {
            Xdist = fabs(Convex[k].x - Convex[i].x);
            Ydist = fabs(Convex[m].y - Convex[j].y);
        }else if(Convex[i].y == Convex[Next(i)].y)
        {
            Xdist = fabs(Convex[k].y - Convex[i].y);
            Ydist = fabs(Convex[m].x - Convex[j].x);
        }else
        {
            double Slope = 1.0 * (Convex[Next(i)].y - Convex[i].y) / (Convex[Next(i)].x - Convex[i].x);
            Xdist = GetDist(Convex[i], Convex[k], Slope);
            Ydist = GetDist(Convex[j], Convex[m], -1.0 / Slope);
        }
        if(i == 1 || 1.0 * Xdist * Ydist < Ans) Ans = 1.0 * Xdist * Ydist;
    }
}

int main()
{
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out", "w", stdout);
    int i;
    scanf("%i", &N);
    for(i = 1; i <= N; ++ i) scanf("%i %i", &V[i].x, &V[i].y);
    if(N >= 2)
    {
        Do_Convex_Hull();
        GetArea();
    }
    printf("%.2lf\n", Ans);
    return 0;
}