Cod sursa(job #1599213)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 13 februarie 2016 18:20:00
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdio>
using namespace std;
ifstream f("rubarba.in");
ofstream g("rubarba.out");
const int NMax = 100005;
const long double eps=1e-16;
const long double pi = 3.141592653;
struct Punct
{
  long double x,y;
  const bool operator == (const Punct& b)
  {
      return this->x==b.x && this->y==b.y;
  }
};
Punct P[NMax],S[NMax];
int N,k;
void Read()
{
    f>>N;
    for(int i=1;i<=N;i++)
        f>>P[i].x>>P[i].y;
}
inline long double dist(Punct a,Punct b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

inline long double Area (Punct A,Punct B, Punct C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-A.y*B.x-B.y*C.x-C.y*A.x;
}
inline long double distToLine(Punct P1,Punct P2,Punct a)
{
    return abs((P2.y-P1.y)*a.x-(P2.x-P1.x)*a.y+P2.x*P1.y-P2.y*P1.x)/dist(P2,P1);
}
inline int cmp(Punct A, Punct B)
{
    return Area(P[1],A,B)>eps;
}
void buildConvexHull()
{
    int Min=1;
    for(int i=2;i<=N;i++)
        if(P[i].y<P[Min].y ||(P[i].y==P[Min].y && P[i].x<P[Min].x))
            Min=i;
    swap(P[1],P[Min]);
    sort(P+2,P+N+1,cmp);
    S[1]=P[1]; S[2]=P[2];k=2;
    for(int i=3;i<=N;i++)
    {
        while(k>=2 && Area(S[k-1],S[k],P[i])<-eps)
            k--;
        S[++k]=P[i];
    }
}

inline Punct findPoint(Punct A,Punct B,Punct C)
{
    if(A==C)
        return A;
    if(B==C)
        return B;
    Punct D;
    long double T=((C.x-A.x)*(B.x-A.x)+(C.y-A.y)*(B.y-A.y))/((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y));
    D.x=A.x+T*(B.x-A.x);
    D.y=A.y+T*(B.y-A.y);
    return D;
}
void Update(Punct& Max,Punct& Min,Punct a)
{
    if(make_pair(Min.x,Min.y)>make_pair(a.x,a.y))
        Min=a;
    if(make_pair(Max.x,Max.y)<make_pair(a.x,a.y))
        Max=a;
}
long double area(long double angle)
{
    long double sn=sin(angle);
    long double cs=cos(angle);
    long double MaxX=-2000000000,MinX=-MaxX,MaxY=MaxX,MinY=MinX;
    for(int i=1;i<k;i++)
    {
        long double X=S[i].x*cs-S[i].y*sn;
        long double Y=S[i].x*sn+S[i].y*cs;
        if(i!=1)
        {
            MaxX=max(MaxX,X);
            MinX=min(MinX,X);
            MaxY=max(MaxY,Y);
            MinY=min(MinY,Y);
        }
        else
        {
            MaxX=MinX=X;
            MaxY=MinY=Y;
        }
    }
    return (MaxX-MinX)*(MaxY-MinY);
}
void Solve()
{
    long double ans=-1;
    S[++k]=S[1];
    for(int i=1;i<k;i++)
    {
        long double MaxDist=0;
        Punct Min=S[i],Max=S[i+1];
        Update(Max,Min,S[i]);
        Update(Max,Min,S[i+1]);
        for(int j=1;j<k;j++)
        {
            Punct X=findPoint(S[i],S[i+1],S[j]);
            Update(Max,Min,X);
            MaxDist=max(MaxDist,distToLine(S[i],S[i+1],S[j]));
        }
        if(ans==-1)
            ans=MaxDist*dist(Max,Min);
        else
            ans=min(ans,MaxDist*dist(Max,Min));
    }
    g<<fixed<<setprecision(2)<<ans<<"\n";
}
long double ternarySearch(long double left,long double right)
{
    if(right-left<=eps)
        return area(left);
    long double mid1=left+(right-left)/3.0;
    long double mid2=right-(right-left)/3.0;
    if(area(mid1)<area(mid2))
        return ternarySearch(left,mid2);
    else
        return ternarySearch(mid1,right);
}
int main()
{
    Read();
    buildConvexHull();
    g<<fixed<<setprecision(2)<<ternarySearch(0,pi/2.0)<<"\n";
    return 0;
}