Cod sursa(job #1003244)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 30 septembrie 2013 00:18:27
Problema Rubarba Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <iostream>
#include <fstream>

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

#define x first
#define y second
#define mp make_pair
#define db long double
#define pdd pair<double,double>
#define LE 100666
#include <algorithm>
#include <cmath>
#include <iomanip>
#define inf (1<<30)

pdd X[LE],hull[LE];
int i,j,n,k,ind,indmax;
db result;

struct trei
{
    db fi,se,th;
};

trei mk3(db i1,db i2,db i3)
{
    trei res;
    res.fi=i1,res.se=i2,res.th=i3;
    return res;
}

trei get_ecc(pdd i1,pdd i2)
{
    db A=i1.y-i2.y;
    db B=i2.x-i1.x;
    db C=i2.y*i1.x-i2.x*i1.y;
    return mk3(A,B,C);
}

db cross(pdd i1,pdd i2,pdd i3)
{
    i3.x-=i1.x,i3.y-=i1.y;
    i2.x-=i1.x,i2.y-=i1.y;
    return i2.y*i3.x-i2.x*i3.y;
}

bool comp(pdd i1,pdd i2)
{
    if (cross(mp(0,0),i1,i2)>0) return true;
    return false;
}

db mdl(db val)
{
  if (val<0) return -val;
  return val;
}

db dist_line(trei dr,pdd i)
{
    db sus=mdl(dr.fi*i.x+dr.se*i.y+dr.th);
    db jos=sqrt(dr.fi*dr.fi+dr.se*dr.se);
    return sus/jos;
}

pdd intr(trei dr1,trei dr2)
{
    db sus=dr2.th*dr1.fi-dr1.th*dr2.fi;
    db jos=(dr1.se*dr2.fi-dr2.se*dr1.fi);
    db Y=sus/jos;
    db X=(-dr1.th-dr1.se*Y)/dr1.fi;
    return mp (X,Y);
}

pdd intr_point_line(trei dr,pdd i)
{
    trei dr2;
    dr2.fi=-dr.se;
    dr2.se=dr.fi;
    dr2.th=-dr2.fi*i.x-dr2.se*i.y;
    return intr(dr,dr2);
}

void c_hull()
{
    hull[1]=X[1];
    hull[2]=X[2];
    k=2;
    int i;

    for(i=3; i<=n; ++i)
    {
        while  (k>1&&cross(hull[k-1],hull[k],X[i])<0) --k;
        hull[++k]=X[i];
    }
}


int main()
{
    f>>n;
    db minim=inf;

    for(i=1; i<=n; ++i)
    {
        f>>X[i].x>>X[i].y;
        if (X[i].y<minim) ind=i,minim=X[i].y;
    }

    swap(X[ind],X[1]);
    for(i=2; i<=n; ++i) X[i].x-=X[1].x,X[i].y-=X[1].y;
    X[1]=mp(0,0);

    sort(X+2,X+n+1,comp);
    c_hull();

    hull[k+1]=hull[1];
   // for(i=1;i<=n;++i) cout<<X[i].x<<" "<<X[i].y<<'\n';
  //  cout<<'\n';

//for(i=1;i<=k;++i) cout<<hull[i].x<<" "<<hull[i].y<<'\n';
result=inf;

    for(i=1; i<=k; ++i)
    {
        trei dr=get_ecc(hull[i],hull[i+1]);
        db dmax=0;

        for(j=1; j<=k; ++j)
        {
            db D=dist_line(dr,hull[j]);
            if (D>dmax)
            {
                dmax=D;
                indmax=j;
            }
        }

        pdd P2=intr_point_line(dr,hull[indmax]);
        trei dr2=get_ecc(hull[indmax],P2);
        db _leftD=0,_rightD=0;

        for(j=1; j<=k; ++j)
            if (cross(hull[indmax],P2,hull[j])<0) _leftD=max(_leftD,dist_line(dr2,hull[j]));
            else _rightD=max(_rightD,dist_line(dr2,hull[j]));

        db swag=dmax*(_rightD+_leftD);
        if (swag<result) result=swag;
    }
 g<<fixed;
 g<<setprecision(2);
    g<<result<<'\n';

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