Cod sursa(job #1780015)

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

ifstream in ( "rubarba.in"  );
ofstream out( "rubarba.out" );

typedef long double f64;

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

vector< pair<int, int> > p;

f64 solve( f64 ang ) {
    f64 xmi = INF, xma = -INF;
    f64 ymi = INF, yma = -INF;

    for( auto pt : p ) {
        pair<f64, f64> pt1 = make_pair( pt.first * sin(ang) - pt.second * cos(ang),
                                        pt.first * cos(ang) + pt.second * sin(ang) );
        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[] ) {

    int n; in >> n; p.resize( n );
    f64 l = 0, r = M_PI / 2, m;

    for( int i = 0; i < n; i ++ )
        in >> p[i].first >> p[i].second;

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

    out << setprecision(2) << fixed << solve(l) << endl;
    return 0;
}