Cod sursa(job #2376347)

Utilizator Mada2003Madalina Scarlat Mada2003 Data 8 martie 2019 15:02:04
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<fstream>
#include<limits>
#include<iomanip>
#include<cmath>
using namespace std;
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
const double PI = 3.141592653589793;
const double INF = numeric_limits<double>::max();
const double EPS = 4e-15;
int n;
pair<int,int> v[100005];
double st, dr, mid;
double solve( double alfa )
{
    double Xmin, Xmax, Ymin, Ymax;
    Xmin = Ymin = INF;
    Xmax = Ymax = -INF;
    for( int i = 1; i <= n; i++ )
    {
        double x = 1.0 * v[i].first * cos( alfa ) - 1.0 * v[i].second * sin( alfa );
        double y = 1.0 * v[i].first * sin( alfa ) + 1.0 * v[i].second * cos( alfa );
        Xmin = min( Xmin, x );
        Xmax = max( Xmax, x );
        Ymin = min( Ymin, y );
        Ymax = max( Ymax, y );
    }
    return ( Xmax - Xmin ) * ( Ymax - Ymin );
}
int main()
{
    fin >> n;
    for( int i = 1; i <= n; i++ )
        fin >> v[i].second >> v[i].first;
    st = 0.0;
    dr = PI / 2.0;
    while( dr - st > EPS )
    {
        mid = ( st + dr ) / 2.0;
        if( solve( mid ) - solve( mid + EPS ) < EPS )
            dr = mid - EPS;
        else
            st = mid + EPS;
    }
    mid = ( st + dr ) / 2.0;
    double area = min( solve(mid), min( solve(mid - EPS), solve(mid + EPS) ) );
    fout << setprecision(5) << fixed << area;
    return 0;
}