Cod sursa(job #843015)

Utilizator stoicatheoFlirk Navok stoicatheo Data 27 decembrie 2012 12:54:07
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.65 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define NM 100010
#define INF 1000000000000.0
#define x first
#define y second
 
 
using namespace std;
 
ifstream f("rubarba.in");
ofstream g("rubarba.out");
 
typedef pair<long long, long long> PI;
typedef pair<double, double> PD;
 
const double EPS=1e-5;
 
long long N;
PI V[NM];
PI ConstT;
 
inline long long Mod (long long X)
{
    return (X<0?-X:X);
}
 
inline long long Sign (const PI& P1, const PI& P2, const PI& P3)
{
    long long S=1LL*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 long long Area (const PI& P1, const PI& P2, const PI& P3)
{
    return Mod(1LL*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);
    }
};
 
long long DoConvexHull ()
{
    long long N,i,j,M;
    long long 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 long long next (long long i)
{
    return (i<N?i+1:1);
}
 
inline long long prev (long long 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));
}
 
double DistP (const PI& A, const PI& B, const PI& P, long long S)
{
    PD C;
 
    if (A.x==B.x)
    {
        C.x=A.x;
        C.y=P.y;
        if (C.x<=max(A.x,B.x) && C.x>=min(A.x,B.x) && C.y<=max(A.y,B.y) && C.y>=min(A.y,B.y))
        {
            if (S==-1) return Dist(A,B);
            return 0;
        }
        if (Dist(B,C)*S<Dist(A,C)*S)
        {
            if (S==-1) return Dist(A,B);
            return 0;
        }
        return Dist(A,C);
    }
 
    if (A.y==B.y)
    {
        C.y=A.y;
        C.x=P.x;
        if (C.x<=max(A.x,B.x) && C.x>=min(A.x,B.x) && C.y<=max(A.y,B.y) && C.y>=min(A.y,B.y))
        {
            if (S==-1) return Dist(A,B);
            return 0;
        }
        if (Dist(B,C)*S<Dist(A,C)*S)
        {
            if (S==-1) return Dist(A,B);
            return 0;
        }
        return Dist(A,C);
    }
 
    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);
 
    if (C.x<=max(A.x,B.x) && C.x>=min(A.x,B.x) && C.y<=max(A.y,B.y) && C.y>=min(A.y,B.y))
    {
        if (S==-1) return Dist(A,B);
        return 0;
    }
    if (Dist(B,C)*S<Dist(A,C)*S)
    {
        if (S==-1) return Dist(A,B);
        return 0;
    }
    return Dist(A,C);
}
 
double ANS=INF;
long long i,j,k;
long long UpD,LeftD,RightD;
 
int main ()
{
    N=DoConvexHull();
 
    {
        i=1;
        j=next(i);
        UpD=next(j);
        RightD=next(j);
        LeftD=prev(1);
 
        for (k=1; k<=N; k++)
        {
            if (Area(V[i],V[j],V[k])>Area(V[i],V[j],V[UpD])) UpD=k;
            if (DistP(V[i],V[j],V[k],1)>DistP(V[i],V[j],V[LeftD],1)) LeftD=k;
            if (DistP(V[i],V[j],V[k],-1)>DistP(V[i],V[j],V[RightD],-1)) RightD=k;
        }
 
        ANS=min(ANS, (1.0 * Area(V[i],V[j],V[UpD]) / Dist(V[i],V[j]) ) * ( DistP(V[i],V[j],V[LeftD],1) + DistP(V[i],V[j],V[RightD],-1) ) );
    }
 
    for (i=2; 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)],1)>=DistP(V[i],V[j],V[LeftD],1) && next(LeftD)!=i)
            LeftD=next(LeftD);
 
        while (DistP(V[i],V[j],V[next(RightD)],-1)>=DistP(V[i],V[j],V[RightD],-1) && next(RightD)!=i)
            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],1) + DistP(V[i],V[j],V[RightD],-1) ) );
    }
 
    g << fixed << setprecision(2) << ANS << '\n';
 
    f.close();
    g.close();
    return 0;
}