Cod sursa(job #786431)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 11 septembrie 2012 13:15:42
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.51 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define NM 100010
#define INF 0x3f3f3f3f
#define x first
#define y second


using namespace std;

ifstream f("rubarba.in");
ofstream g("rubarba.out");

typedef pair<int, int> PI;
typedef pair<double, double> PD;

const double EPS=1e-5;

int N;
PI V[NM];
PI ConstT;

inline int Mod (int X)
{
    return (X<0?-X:X);
}

inline int Sign (const PI& P1, const PI& P2, const PI& P3)
{
    int S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
    if (S==0) return 0;
    return (S<0?-1:1);
}

inline int Area (const PI& P1, const PI& P2, const PI& P3)
{
    return Mod(P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y);
}

inline double Tang (const PI& P1,const PI& P2)
{
    if (P1.x==P2.x) return INF;
    return (1.0*P1.y-1.0*P2.y)/(1.0*P1.x-1.0*P2.x);
}

struct TangCMP
{
    bool operator () (const PI& a, const PI& b) const
    {
        return Tang(a,ConstT)<Tang(b,ConstT);
    }
};

int DoConvexHull ()
{
    int N,i,j,M;
    int S[NM];
    PI A[NM],B[NM];
    B[1].x=B[1].y=INF;
    f >> N;
    for (i=1; i<=N; i++)
    {
        f >> A[i].x >> A[i].y;
        if (A[i].x<B[1].x || (A[i].x==B[1].x && A[i].y<B[1].y))
            B[1]=A[i];
    }
    M=1;
    for (i=1; i<=N; i++)
        if (B[1].x!=A[i].x || B[1].y!=A[i].y)
            B[++M]=A[i];

    ConstT=B[1];
    sort(B+2,B+M+1,TangCMP());

    N=M;
    S[M=1]=1;

    for (i=2; i<=N; i++)
    {
        while (M>=2 && Sign(B[S[M-1]],B[S[M]],B[i])<0) --M;
        S[++M]=i;
    }

    for (i=2; i<=M; i++)
        V[i-1]=B[S[i]];
    V[M]=B[S[1]];

    return M;
}

inline int next (int i)
{
    return (i<N?i+1:1);
}

inline int prev (int i)
{
    return (i>1?i-1:N);
}

double Dist (const PD& a, const PD& b)
{
    return sqrt(1.0*(a.x-b.x)*(a.x-b.x) + 1.0*(a.y-b.y)*(a.y-b.y));
}

bool Equal (double a, double b)
{
    return fabs(a-b)<=EPS;
}

double DistP (const PI& A, const PI& B, const PI& P)
{
    PD C;
    double d1,d2;

    if (A.x==B.x)
    {
        C.x=A.x;
        C.y=P.y;
        d1=Dist(A,C);
        d2=Dist(B,C);
        if (Equal(d1+d2,Dist(A,B))) return -d1;
        return d1;
    }

    if (A.y==B.y)
    {
        C.y=A.y;
        C.x=P.x;
        d1=Dist(A,C);
        d2=Dist(B,C);
        if (Equal(d1+d2,Dist(A,B))) return -d1;
        return d1;

    }

    double m1=1.0*(A.y-B.y)/(A.x-B.x);
    double m2=-1.0/m1;

    C.x=1.0*(A.y-P.y-m1*A.x+m2*P.x)/(m2-m1);
    C.y=A.y+m1*(C.x-A.x);

    d1=Dist(A,C);
    d2=Dist(B,C);
    if (Equal(d1+d2,Dist(A,B))) return -d1;
    return d1;
}

double ANS=INF;
int i,j;
int UpD,LeftD,RightD;

int main ()
{
    N=DoConvexHull();

    LeftD=prev(1);
    UpD=next(next(1));
    RightD=UpD;

    for (i=1; i<=N; i++)
    {
        j=next(i);

        while (Area(V[i],V[j],V[next(UpD)])>Area(V[i],V[j],V[UpD]))
            UpD=next(UpD);


        while (DistP(V[i],V[j],V[next(LeftD)])>DistP(V[i],V[j],V[LeftD]) || DistP(V[i],V[j],V[LeftD])<0)
            LeftD=next(LeftD);

        while (DistP(V[j],V[i],V[next(RightD)])>DistP(V[j],V[i],V[RightD]) || DistP(V[j],V[i],V[RightD])<0)
            RightD=next(RightD);


        ANS=min(ANS, (1.0 * Area(V[i],V[j],V[UpD]) / Dist(V[i],V[j]) ) * ( DistP(V[i],V[j],V[LeftD]) + DistP(V[i],V[j],V[RightD]) ) );
    }

    g << fixed << setprecision(2) << ANS << '\n';

    f.close();
    g.close();
    return 0;
}