Cod sursa(job #1780025)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 15 octombrie 2016 19:57:59
Problema Rubarba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 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 = 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[] ) {

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

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

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

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