Cod sursa(job #1308573)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 4 ianuarie 2015 13:42:48
Problema Rubarba Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.5 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define Nmax 100005
#define INF 2000000000
#define eps 0.000000001

using namespace std;
ofstream fout ("rubarba.out");

int n,Up[Nmax],Left[Nmax],Right[Nmax],st[Nmax],top,VARF;
bool fr[Nmax];
struct Point
{
    long double x,y;
    bool operator <(const Point &A) const
    {
        return y<A.y;
    }
} a[Nmax];

inline long long Plan(Point A, Point B, Point C)
{
    return (B.y-A.y)*C.x+(A.x-B.x)*C.y+B.x*A.y-A.x*B.y;
}

inline void Convex_Hull()
{
    sort(a+1,a+n+1);
    int i,sign=1;
    top=2;
    st[1]=1; st[2]=2; fr[2]=true;
    for(i=3;i;i+=sign)
    {
        if(fr[i]) continue;
        if(i==n) sign=-1;
        while(top>1 && Plan(a[st[top-1]],a[st[top]],a[i])>=0) fr[st[top--]]=false;
        st[++top]=i; fr[i]=true;
        if(i==n)
        {
            sign=-1; VARF=top;
        }
    }
}

inline long double Arie(Point A, Point B, Point C)
{
    return 0.5*fabs(A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-A.x*C.y-B.x*A.y);
}

inline long double D(Point A, Point B)
{
    return sqrt((long double)(A.x-B.x)*(A.x-B.x)+(long double)(A.y-B.y)*(A.y-B.y));
}

inline long double Dist(Point A, Point B, Point C)
{
    return (2.0*Arie(A,B,C))/D(B,C);
}

inline int Next(int p)
{
    ++p;
    if(p>n) p-=n;
    return p;
}

inline Point Proiectie (Point A, Point B, Point C)
{
    long double alfa,beta,gama,alfa1,beta1,gama1;
    alfa=C.y-B.y; beta=B.x-C.x; gama=C.x*B.y-B.x*C.y;
    alfa1=-beta; beta1=alfa; gama1=-alfa1*A.x-beta1*A.y;
    Point sol;
    sol.y=(alfa1*gama-gama1*alfa)/(beta1*alfa-alfa1*beta);
    if(!alfa) sol.x=A.x;
    else
        sol.x=(-gama-beta*sol.y)/alfa;
    return sol;
}

inline bool Ok2(Point A, Point B, Point C, Point DD);

inline bool Ok1(Point A, Point B, Point C, Point DD)
{
    if(A.x>B.x) return Ok2(B,A,C,DD);
    if(A.x==B.x)
    {
        if(A.y<B.y)
            return DD.y-C.y<eps;
        return DD.y-C.y>eps;
    }
    C=Proiectie(C,A,B); DD=Proiectie(DD,A,B);
    return DD.x-C.x<eps;
}

inline bool Ok2(Point A, Point B, Point C, Point DD)
{
    if(A.x>B.x) return Ok1(B,A,C,DD);
    if(A.x==B.x)
    {
        if(A.y<B.y)
            return DD.y-C.y>eps;
        return DD.y-C.y<eps;
    }
    C=Proiectie(C,A,B); DD=Proiectie(DD,A,B);
    return DD.x-C.x>eps;
}

int main()
{
    int i,p;
    long double sol=INF;
    Point X,Y,Z;
    ifstream fin ("rubarba.in");
    fin>>n;
    for(i=1;i<=n;++i) fin>>a[i].x>>a[i].y;
    Convex_Hull();
    n=top-1;
    //for(i=1;i<=n;++i) fout<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
    for(i=1,p=3;i<=n;++i)
    {
        while(Dist(a[st[Next(p)]],a[st[i]],a[st[i+1]])-Dist(a[st[p]],a[st[i]],a[st[i+1]])>eps) p=Next(p);
        Up[i]=p;
    }
    for(i=1,p=n;i<=n;++i)
    {
        if(i+1==p) p=Next(p);
        while(Ok1(a[st[i]],a[st[i+1]],a[st[p]],a[st[Next(p)]])) p=Next(p);
        Left[i]=p;
    }
    for(i=1,p=3;i<=n;++i)
    {
        if(i+1==p) p=Next(p);
        while(Ok2(a[st[i]],a[st[i+1]],a[st[p]],a[st[Next(p)]])) p=Next(p);
        Right[i]=p;
    }
    for(i=1;i<=n;++i)
    {
        X=Proiectie(a[st[Up[i]]],a[st[i]],a[st[i+1]]);
        Y=Proiectie(a[st[Left[i]]],a[st[i]],a[st[i+1]]);
        Z=Proiectie(a[st[Right[i]]],a[st[i]],a[st[i+1]]);
        sol=min(sol,D(X,a[st[Up[i]]])*D(Y,Z));
        //fout<<Left[i]<<"\n";
    }
    fout<<setprecision(5)<<fixed;
    fout<<sol;
    //fout<<Ok1(a[st[5]],a[st[1]],a[st[3]],a[st[4]]);
    return 0;
}