Cod sursa(job #1210623)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 20 iulie 2014 17:21:35
Problema Rubarba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 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;

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

void convexHull();

int main()
{
    int i,j;
    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();

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

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

    sol=INF;

    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<<alfa*180.0/PI<<" ";

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

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

        sol=min(sol,(xmax-xmin)*(ymax-ymin));

        //fout<<(xmax-xmin)*(ymax-ymin)<<'\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];
    }
}