Cod sursa(job #1438213)

Utilizator geniucosOncescu Costin geniucos Data 19 mai 2015 12:55:45
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<cstdio>
#include<fstream>
#include<iomanip>
#include<cmath>

using namespace std;

int T, N, x[100009], y[100009];
long double maxx, minx, maxy, miny, cs, sn;

void Get (long double unghi)
{
    cs = (long double) cos (unghi);
    sn = (long double) sin (unghi);

    for (int i=1; i<=N; i++)
    {
        long double X, Y;
        X = (long double) x[i] * cs - y[i] * sn;
        Y = (long double) x[i] * sn + y[i] * cs;
        if (i == 1)
            minx = maxx = X, miny = maxy = Y;
        else
        {
            if (X < minx)
                minx = X;
            if (X > maxx)
                maxx = X;
            if (Y < miny)
                miny = Y;
            if (Y > maxy)
                maxy = Y;
        }
    }
}

long double F (long double unghi)
{
    Get (unghi);
    return (long double) (maxx - minx) * (maxy - miny);
}

long double solve (long double st, long double dr)
{
    if (dr - st <= 1e-16)
        return st;

    long double mid1 = st + (dr - st) / 3.0;
    long double mid2 = dr - (dr - st) / 3.0;
    long double c1 = F (mid1), c2 = F (mid2);

    if (c1 < c2)
        return solve (st, mid2);
    return solve (mid1, dr);
}

int main()
{
freopen ("rubarba.in", "r", stdin);
ofstream g ("rubarba.out");

scanf ("%d", &N);
for (int i=1; i<=N; i++)
    scanf ("%d %d", &x[i], &y[i]);

long double unghi = solve (0, (long double)M_PI / 2.0);
g << fixed << setprecision (2) << F (unghi);

return 0;
}