Cod sursa(job #2067890)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 16 noiembrie 2017 22:19:49
Problema Rubarba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#define pi 3.1415926535
#define DIM 100002
#define INF 1e12

using namespace std;

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

int n;

long double minim = INF, eps = 1e-13;

long double convert(long double unghi){
    return (unghi / 180.0) * pi;
}

struct punct{
    long double x, y;
}pct[DIM];

long double calc(double unghi){
    //unghi = convert(unghi);
    long double xmax = -INF, xmin = INF, ymax = -INF, ymin = INF;
    for(int i = 1; i <= n; ++ i){
        long double x = pct[i].x * cos(unghi) - pct[i].y * sin(unghi);
        long double y = pct[i].x * sin(unghi) + pct[i].y * cos(unghi);
        xmax = max(x, xmax);
        xmin = min(x, xmin);
        ymax = max(y, ymax);
        ymin = min(y, ymin);
    }
    return (xmax - xmin) * (ymax - ymin);
}

int main()
{
    f>>n;
    for(int i = 1; i <= n; ++ i)
        f>>pct[i].x>>pct[i].y;

    long double st = 0, dr = M_PI;

    //g<<M_PI<<" "

    while(dr - st > eps){
        long double mid = (st + dr) / 2.0;
        long double valmid = calc(mid);
        long double valmid1 = calc(mid + eps);
        if(valmid <= valmid1){
            dr = mid;
            if(valmid < minim)
                minim = valmid;
        }
        else{
            st = mid;
            if(valmid1 < minim)
                minim = valmid1;
        }
    }

    g<<setprecision(2)<<fixed<<minim;


    return 0;
}