Cod sursa(job #1438201)

Utilizator geniucosOncescu Costin geniucos Data 19 mai 2015 12:25:37
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include<cstdio>
#include<cmath>

using namespace std;

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

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

    for (int i=1; i<=N; i++)
    {
        double X, Y;
        X = (double) x[i] * cs - y[i] * sn;
        Y = (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;
        }
    }
}

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

double solve (double st, double dr)
{
    if (dr - st <= 0.000001)
        return st;

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

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

void afis (double X, double Y)
{
    double a, b;
    b = (double) Y * cs - X * sn;
    a = (double) X * cs + Y * sn;
    printf ("%.8lf %.8lf\n", a, b);
}

int main()
{
freopen ("rubarba.in", "r", stdin);
freopen ("rubarba.out", "w", stdout);

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

double unghi = solve (0, 90);
printf ("%.2lf\n", F (unghi));
/*Get (unghi);
afis (minx, miny);
afis (minx, maxy);
afis (maxx, miny);
afis (maxx, maxy);*/

return 0;
}