Cod sursa(job #1778626)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 13 octombrie 2016 22:28:39
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
// Cautare ternara pe unghiul rotatiei planului
#include <bits/stdc++.h>
using namespace std;
typedef long double f64;

const int SPQR = 100005; // Ave Imperator, morituri te salutant!
const f64  INF = 1e12,
           EPS = 1e-17;

struct PTX {
    int x, y;
};

int n;
PTX pts[SPQR];

f64 calc(f64 ang) {
    f64 x, y, sn, cs, min_x, min_y, max_x, max_y;

    min_x = min_y = INF,
    max_x = max_y =-INF;
    sn = sin(ang);
    cs = cos(ang);

    for(int i=0; i<n; ++i) {
        x = pts[i].x * cs - pts[i].y * sn;
        y = pts[i].x * sn + pts[i].y * cs;

        min_x = min(min_x, x);
        max_x = max(max_x, x);

        min_y = min(min_y, y);
        max_y = max(max_y, y);
    }

    return (max_x - min_x) * (max_y - min_y);
}

int main(void) {
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out", "w", stdout);
    f64 x, y, st, dr, med;

    st = 0.0;
    dr = atan(1) * 2;

    scanf("%d", &n);
    for(int i=0; i<n; ++i)
        scanf("%d%d", &pts[i].x, &pts[i].y);

    while(dr-st >= EPS) {
        med = (st + dr) / 2;
        if(calc(med) > calc(med+EPS))
            st = med;
        else
            dr = med;
    }

    printf("%.2Lf\n", calc(st));

    return 0;
}