Cod sursa(job #1451942)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 19 iunie 2015 00:58:17
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <iomanip>

using namespace std;

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

vector <pair <int,int> > V;

int N;
long double p, u, mid1, mid2;
const long double PI = 3.141592653589;
const long double eps = 1e-16;

long double F(long double angle){
    long double s=sin(angle);
    long double c=cos(angle);

    long double maxx = c*V[0].first - s*V[0].second;
    long double minx = maxx;
    long double maxy = s*V[0].first+c*V[0].second;
    long double miny = maxy;

    for(std::vector <pair <int,int> >::iterator it=V.begin();it!=V.end();it++){

        long double x = c * it->first - s * it->second ;
        long double y = s * it->first + c * it->second;

        maxx = max( maxx ,x);
        minx = min( minx ,x);

        maxy = max( maxy, y);
        miny = min( miny, y);
    }

    return (maxx - minx) * (maxy - miny);
}
int main(){

    fin >> N;

    for(int i=1;i<=N;i++){
        int x,y;
        fin>>x>>y;
        V.push_back(make_pair(x,y));
    }

    p = 0;
    u = PI * 0.5 ;

    while(u - p >= eps){

        mid1 = p + (u - p)/3.0;
        mid2 = u - (u - p)/3.0;

        if(F(mid1) < F(mid2))
            u = mid2;
        else
            p = mid1;

    }

    fout << setprecision(2) << fixed << F(p) << "\n";

    fin.close();    fout.close();

    return 0;
}