Cod sursa(job #1780022)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 15 octombrie 2016 19:56:50
Problema Rubarba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <vector>
using namespace std;

typedef long double f64;

const int DIM = 1e5;
const f64 EPS = 1e-17;
const f64 INF = 1e12;

vector< pair<int, int> > p;

f64 solve( f64 ang ) {
    f64 xmi = INF, xma = -INF, sn = sin( ang );
    f64 ymi = INF, yma = -INF, cs = cos( ang );

    for( auto pt : p ) {
        pair<f64, f64> pt1 = make_pair( pt.first * sn - pt.second * cs,
                                        pt.first * cs + pt.second * sn );
        xmi = min( xmi, pt1.first  ); xma = max( xma, pt1.first  );
        ymi = min( ymi, pt1.second ); yma = max( yma, pt1.second );
    }

    return (xma - xmi) * (yma - ymi);
}

int main( int argc, const char *argv[] ) {

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

    int n; scanf( "%d", &n ); p.resize( n );
    f64 l = 0, r = atan(1) * 2, m;

    for( int i = 0; i < n; i ++ )
        scanf( "%d %d", &p[i].first, &p[i].second );

    while( r - l >= EPS ) {
        m = (l + r) / 2;
        ( solve(m) > solve(m + EPS) ) ? ( l = m ) : ( r = m );
    }

    printf( "%.2Lf\n", solve(m) );
    return 0;
}