Cod sursa(job #2067875)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 16 noiembrie 2017 21:52:03
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#define pi 3.14159265
#define eps 4e-15
#define DIM 100002
#define INF 1e12

using namespace std;

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

int n;

double minim = INF;

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

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

double calc(double unghi){
    unghi = convert(unghi);
    double xmax = -INF, xmin = INF, ymax = -INF, ymin = INF;
    for(int i = 1; i <= n; ++ i){
        double x = pct[i].x * cos(unghi) - pct[i].y * sin(unghi);
        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 + eps) * (ymax - ymin + eps);
}

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

    double st = 0, dr = 180;

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

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


    return 0;
}