Cod sursa(job #1779780)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 15 octombrie 2016 16:43:55
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" );

const    int DIM = 1e+5;
const double EPS = 1e-9;
const double INF = 1e12;

vector< pair<double, double> > p;

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

    for( auto pt : p ) {
        pair<double, double> 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 );
    double l = 0, r = M_PI / 2, m;

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

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

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