Cod sursa(job #1210645)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 20 iulie 2014 18:17:14
Problema Rubarba Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.57 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iomanip>

using namespace std;

typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef long long int lld;
const int NMAX = 100000+5;
const int INF = (1<<30);
const double PI = acos(-1.0);

ifstream fin("rubarba.in");
ofstream fout("rubarba.out");

int N,M;
PII P[NMAX];
PII H[NMAX];
double sol;
double A,B,C;

inline lld crossProd(PII A,PII B,PII C)
{
    return (B.first-A.first)*(C.second-A.second)-(C.first-A.first)*(B.second-A.second);
}

inline bool cmp(PII A,PII B)
{
    return crossProd(P[1],A,B)>0;
}

inline PDD rotate(PII A,double alfa)
{
    alfa=-alfa;
    double x,y;
    x=A.first*cos(alfa)-A.second*sin(alfa);
    y=A.first*sin(alfa)+A.second*cos(alfa);
    return make_pair(x,y);
}

inline void ecuation(PII A,PII B,double &a,double &b,double &c)
{
    a=A.second-B.second;
    b=B.first-A.first;
    c=A.first*B.second-A.second*B.first;
}

inline void ecuation(PII A,double m,double &a,double &b,double &c)
{
    if(m==0.0)
    {
        a=0.0;
        b=1.0;
        c=A.second;
        return;
    }
    if(m==INF)
    {
        a=1.0;
        b=0.0;
        c=A.first;
        return;
    }
    a=m;
    b=-1.0;
    c=A.second-m*A.first;
}

inline double dist(double a,double b,double c,PII X) // dist(AB,X)
{
    return fabs(a*X.first+b*X.second+c)/sqrt(a*a+b*b);
}

double bs(int lo,int hi)
{
    if(lo>hi) return 0.0;
    int mi=(lo+hi)/2;
    double a,b,c;
    a=dist(A,B,C,H[mi-1]);
    b=dist(A,B,C,H[mi]);
    c=dist(A,B,C,H[mi+1]);
    if(a<=b && b>=c) return b;
    if(a<=b && b<=c) return bs(mi+1,hi);
    if(a>=b && b>=c) return bs(lo,mi-1);
    return max(bs(lo,mi-1),bs(mi+1,hi));
}

void convexHull();

int main()
{
    int i,j;
    double x,m,y,z,alfa;
    double xmin,ymin,xmax,ymax;
    double heigth,width;
    PDD Q,W;

    fin>>N;

    for(i=1; i<=N; i++)
        fin>>P[i].first>>P[i].second;

    convexHull();

    if(M<=2)
    {
        fout<<fixed<<setprecision(2)<<sol;
        return 0;
    }

    H[0]=H[M];
    H[M+1]=H[1];

    sol=INF;
    xmin=INF;

    x=H[2].first-H[1].first;
    y=H[2].second-H[1].second;
    z=sqrt(x*x+y*y);
    alfa=acos(x/z);
    if(y<0) alfa=-alfa;

    for(i=1; i<=M; i++)
    {
        Q=rotate(H[i],alfa);
        if(Q.first<xmin)
        {
            xmin=Q.first;
            j=i;
        }
    }

    for(i=1; i<=M; i++)
    {
        ecuation(H[i],H[i+1],A,B,C);
        heigth=bs(1,M);
        //fout<<heigth<<' ';

        x=H[i+1].first-H[i].first;
        y=H[i+1].second-H[i].second;
        z=sqrt(x*x+y*y);
        alfa=acos(x/z);
        if(y<0) alfa=-alfa;

        for(; j<=M; j++)
        {
            Q=rotate(H[j],alfa);
            W=rotate(H[j+1],alfa);
            if(Q.first<W.first) break;
            if(j==M) j=0;
        }

        //fout<<" !"<<j<<"! ";

        if(B==0.0) m=INF;
        else m=-A/B;

        if(m==INF) m=0.0;
        else if(m==0.0) m=INF;
        else m=-1.0/m;

        ecuation(H[j],m,A,B,C);
        width=bs(1,M);
        //fout<<width<<" > ";
        //fout<<heigth*width<<'\n';

        sol=min(sol,heigth*width);
    }

    fout<<fixed<<setprecision(2)<<sol;

    return 0;
}

void convexHull()
{
    int i;

    sort(P+1,P+N+1);
    sort(P+2,P+N+1,cmp);

    H[++M]=P[1];
    H[++M]=P[2];

    for(i=3; i<=N; i++)
    {
        while(M>=2 && crossProd(H[M-1],H[M],P[i])<0) M--;
        H[++M]=P[i];
    }
}