Cod sursa(job #920427)

Utilizator Theorytheo .c Theory Data 20 martie 2013 13:10:50
Problema Rubarba Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.2 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];

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

    return V1.x * (V2.y - V3.y)  + 1LL * V2.x * (V3.y - V1.y) + 1LL * V3.x * (V1.y - V2.y);
}

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 + C)/ sqrt(1 + A * A);}

inline long double DistParametric(const PI P ,const DB A, const DB B, const DB C){ return fabs((P.x * A + B * P.y + 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]) > 0) StackSize--;
        Stack[++StackSize] = V[i];
    }

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


struct cmp{

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

void ConvexHull(){

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

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

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

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 DetEcuationParametric( PI P1,PI P2, DB &A,DB &B, DB &C){


    A = P1.y - P2.y;
    B = P2.x - P1.x;
    C = P1.x * P2.y - P1.y * P2.x;
}

void Solve(){

    DB MinArea = INF;

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

       DB A1, B1, C1, A2, B2, C2, A, B, C;
       DB MaxHorizontal = 0.0 ;DB MaxVertical = -INF ; DB MinVertical = INF;

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

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

            DB H = fabs(DistParametric(Convex[j], A, B, C));
            DB H2 = fabs(Dist(Convex[j] , A1, B1, C1));

            if(H > MaxHorizontal) MaxHorizontal = H;

            H = Dist(Convex[j], A2, B2, C2);
            if(H > MaxVertical) MaxVertical = H;
            if(H < MinVertical) MinVertical = H;


        }
        if(MinArea > MaxHorizontal * (MaxVertical - MinVertical))
            MinArea = MaxHorizontal * (MaxVertical - MinVertical);

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

}

int main(){

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