Cod sursa(job #1780416)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 16 octombrie 2016 10:20:19
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("rubarba.in");
ofstream g("rubarba.out");
const double EPS=4e-15,Xp=1e12;
int n,i;
pair<int,int> p[1<<17];
double solve(double ang)
{
    double xmi=Xp,xma=-Xp,ymi=Xp,yma=-Xp;
    double si=sin(ang),co=cos(ang);
    for(i=0;i<n;++i)
    {
        double a=si*p[i].first-co*p[i].second;
        double b=co*p[i].first+si*p[i].second;
        xmi=min(xmi,a);
        xma=max(xma,a);
        ymi=min(ymi,b);
        yma=max(yma,b);
    }
    return (xma-xmi)*(yma-ymi);
}
int main()
{
    f>>n;
    double l=0,r=M_PI/2,m;
    for(i=0;i<n;++i)
        f>>p[i].first>>p[i].second;
    while(r-l>=EPS)
    {
        m=(r+l)/2;
        (solve(m)>=solve(m+EPS))?l=m:r=m;
    }
    g<<fixed<<setprecision(2)<<solve(m);
    return 0;
}