Cod sursa(job #1438211)

Utilizator geniucosOncescu Costin geniucos Data 19 mai 2015 12:50:57
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 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 ((long double) unghi * M_PI);
    sn = (long double) sin ((long double) unghi * M_PI);

    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-12)
        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);
}

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);
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, 180);
g << fixed << setprecision (2) << F (unghi);
/*Get (unghi);
afis (minx, miny);
afis (minx, maxy);
afis (maxx, miny);
afis (maxx, maxy);*/

return 0;
}