Cod sursa(job #920334)

Utilizator Theorytheo .c Theory Data 20 martie 2013 10:44:42
Problema Rubarba Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 kb
#include<fstream>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<vector>

using namespace std;

#define PI pair<int, int>
#define LL long long
#define DB long double
#define x first
#define y second

ifstream fin("rubarba.in");
ofstream fout("rubarba.out");

const int Nmax = 100009;
const double INF = 100000000.00;

int N; int K; int StackSize;int Sk;int First;

PI V[Nmax], Stack[Nmax], Convex[Nmax];

double Horizontal, Vetrtical, Ans;

LL Det(const PI V1,const PI V2,const PI V3){

    return V1.x * V2.y + V2.x * V3.y + V3.x * V1.y - V1.y * V2.x - V2.y * V3.x - V3.y * V1.x;
}

void Read() {

    fin >> N; First = 1;

    for(int i = 1; i <= N; ++i){
        fin >> V[i].x >> V[i].y;
        if(V[i].x < V[First].x || (V[i].x == V[First].x && V[i].y < V[First].y )) First = i;
    }
    swap(V[1], V[First]);
}

inline long double Dist(const PI P ,const DB A, const DB B, const DB C){ return (P.x * A + P.y * B + C)/ sqrt(B * B + A * A);}

void AddConvex(){
    StackSize = 1;
    Stack[StackSize] = V[1]; Stack[++StackSize] = V[2];

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

    for(int i = 1; i <= StackSize; ++i) Convex[++K] = Stack[i];
}

bool cmp2(const PI P1, const PI P2){

    return (P1.y > P2.y )|| ((P1.y == P2.y) && (P1.x > P2.x));
}

bool cmp(const PI P1, const PI P2){
    return Det(V[1], P1, P2) < 0;
}

void ConvexHull(){

    sort(V + 2, V + N + 1, cmp); AddConvex(); Sk = K;


    //for(int i = K + 1; i <= 2 * K; ++i)
    Convex[K + 1] = Convex[1];

    Convex[2 * K + 1] = Convex[1];
    //sort(V + 1, V + N + 1, cmp); AddConvex();

}

double Tg(const PI &P1, const PI &P2){
    if(P1.x == P2.x)  return INF;

    return (P1.y - P2.y) / (P1.x - P2.x);
}

int Next(int X){
    if(X == K) return 1;
    return X + 1;
}

void DetEcuation(const PI P1,const PI P2, DB &A1,DB &B1, DB &C1, DB &A2, DB &B2, DB &C2){

    A1 = Tg(P1, P2);

    if(A1 == 0) A2 = -INF;
    else A2 = -1.0/ A1;

    B1 = B2 = -1.0;
    C1 = P1.y - A1 * P1.x;
    DB X = (P1.x + P2.x) / 2.0;DB Y = (P1.y + P2.y) / 2.0;

    C2 = Y - A2 * X;
}

void Solve(){

    double long MinArea = INF;

    //fout << Sk <<'\n';

    for(int i = 1; i <= K ; ++i){

       double long A1, B1, C1, A2, B2, C2;
       double long MaxHorizontal = 0.0 ;DB MaxVertical = 0.0 ; DB MinVertical = 0.0;

        DetEcuation(Convex[i], Convex[i + 1], A1, B1, C1, A2, B2, C2);

        //fout << Convex[i].x <<" " << Convex[i].y <<'\n';

        for(int j = 1 ; j <= K; ++j){

            //fout << Convex[j].x <<" " << Convex[j].y <<'\n';

            DB H = fabs(Dist(Convex[j], A1, B1, C1));
            DB V1 = Dist(Convex[j], A2, B2, C2);

            if(H > MaxHorizontal) MaxHorizontal = H;
            if(V1 > MaxVertical) MaxVertical = V1;
            if(V1 < MinVertical) MinVertical = V1;


        }
        //fout << MaxHorizontal <<" " << MaxVertical - MinVertical<<'\n';
        if(MinArea > MaxHorizontal * (MaxVertical - MinVertical))
            MinArea = MaxHorizontal * (MaxVertical - MinVertical);

    }
    fout <<fixed << setprecision(2) << MinArea;

}

int main(){

    Read (); ConvexHull (); Solve(); return 0;
}