Cod sursa(job #1210484)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 20 iulie 2014 02:29:57
Problema Rubarba Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.17 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);

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

int N,M;
PII P[NMAX];
PII H[NMAX];
double area,sol;

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=2*3.14159-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);
}

void convexHull();

int main()
{
    int i,a,b,c,d;
    double x,y,z,alfa;
    double xmin,ymin,xmax,ymax;
    PDD Q;

    fin>>N;

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

    convexHull();

    for(i=1; i<=M+1; i++)
        H[M+i]=H[i];

    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;

    xmin=ymin=INF;
    xmax=ymax=-INF;

    for(i=1; i<=M; i++)
    {
        Q=rotate(H[i],alfa);
        if(Q.first<xmin)
        {
            xmin=Q.first;
            a=i;
        }
        if(Q.second<ymin)
        {
            ymin=Q.second;
            b=i;
        }
        if(Q.first>xmax)
        {
            xmax=Q.first;
            c=i;
        }
        if(Q.second>ymax)
        {
            ymax=Q.second;
            d=i;
        }
    }

    //fout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n';

    sol=area=(xmax-xmin)*(ymax-ymin);

    for(i=1; i<=M; i++)
    {
        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;

        //fout<<x<<" "<<y<<" "<<z<<" "<<alfa*180.0/3.14<<'\n';

        xmin=ymin=INF;
        xmax=ymax=-INF;

        Q=rotate(H[a+i-1],alfa);
        xmin=min(xmin,Q.first);
        ymin=min(ymin,Q.second);
        xmax=max(xmax,Q.first);
        ymax=max(ymax,Q.second);

        Q=rotate(H[b+i-1],alfa);
        xmin=min(xmin,Q.first);
        ymin=min(ymin,Q.second);
        xmax=max(xmax,Q.first);
        ymax=max(ymax,Q.second);

        Q=rotate(H[c+i-1],alfa);
        xmin=min(xmin,Q.first);
        ymin=min(ymin,Q.second);
        xmax=max(xmax,Q.first);
        ymax=max(ymax,Q.second);

        Q=rotate(H[d+i-1],alfa);
        xmin=min(xmin,Q.first);
        ymin=min(ymin,Q.second);
        xmax=max(xmax,Q.first);
        ymax=max(ymax,Q.second);

        area=(xmax-xmin)*(ymax-ymin);

        sol=min(sol,area);
        //fout<<fixed<<setprecision(2)<<area<<'\n';
    }

    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];
    }
}