Cod sursa(job #2627705)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 11 iunie 2020 23:24:59
Problema Rubarba Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int NMAX = 100000;
const double eps = 4.e-15;
const double PI = 2.0 * acos(0.0);
const double INF = 2.e9;
struct POINT
{
    double x , y;
    POINT(double tx = 0.0 , double ty = 0.0)
    {
        x = tx;
        y = ty;
    }
};
POINT P[NMAX + 5];
int n;
double arie(double angle)
{
    int i;
    double sinus , cosinus , x , y , xmin , ymin , xmax , ymax;
    sinus = sin(angle);
    cosinus = cos(angle);
    xmax = ymax = -INF;
    xmin = ymin = INF;
    for(i = 1 ; i <= n ; i ++)
    {
        x = P[i].x * cosinus - P[i].y * sinus;
        y = P[i].x * sinus + P[i].y * cosinus;
        xmax = max(xmax , x);
        ymax = max(ymax , y);
        xmin = min(xmin , x);
        ymin = min(ymin , y);
    }
    return (xmax - xmin) * (ymax - ymin);
}
int main()
{
    freopen("rubarba.in" , "r" , stdin);
    freopen("rubarba.out" , "w" , stdout);
    int i;
    double x , y , st , dr , med;
    scanf("%d" , &n);
    for(i = 1 ; i <= n ; i ++)
    {
        scanf("%lf%lf" , &x , &y);
        P[i] = POINT(x , y);
    }
    st = 0.0;
    dr = PI;
    while(dr - st > eps)
    {
        med = (st + dr) / 2.0;
        if(arie(med) - arie(med + eps) < eps)
            dr = med - eps;
        else
            st = med + eps;
    }
    med = (st + dr) / 2.0;
    printf("%lf" , min(arie(med) , min(arie(med + eps) , arie(med - eps))));
    return 0;
}