Cod sursa(job #1723592)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 30 iunie 2016 23:45:06
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
/** Baga-mi-as pula in precizia voastra! (C) 2016 Vlad Dumitru */

#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

const int N_MAX = 100010;
const long double Eps = 1e-17;
const long double Inf = 1e20;
const long double Pi = acos(-1.0);

int N;
long double X[N_MAX];
long double Y[N_MAX];

/** This function has a minimum which will be determined by the ternary search */
long double getBoxArea(long double Rotation) {
  long double xMin = Inf, xMax = -Inf, yMin = Inf, yMax = -Inf, Sin = sin(Rotation), Cos = cos(Rotation);
  for(int i = 1; i <= N; i++) {
    long double xNew = X[i] * Cos - Y[i] * Sin;
    long double yNew = X[i] * Sin + Y[i] * Cos;
    xMax = max(xMax, xNew);
    yMax = max(yMax, yNew);
    xMin = min(xMin, xNew);
    yMin = min(yMin, yNew);
  }
  return (xMax - xMin) * (yMax - yMin);
}

/** Employing the great trick of comparing Mid to Mid + Eps -- Equivalent to comparing the thirds */
long double ternarySearch() {
  long double Lo = 0, Hi = Pi / 2;
  while(Lo + Eps < Hi) {
    long double Mid = (Lo + Hi) * 0.5;
    if(getBoxArea(Mid) > getBoxArea(Mid + Eps)) Lo = Mid;
    else Hi = Mid; 
  }
  return Lo;
}

int main() {
  ifstream f("rubarba.in");
  ofstream g("rubarba.out");
  
  f >> N;
  for(int i = 1; i <= N; i++)
    f >> X[i] >> Y[i];
    
  g << setprecision(2) << fixed << getBoxArea(ternarySearch());
  
  return 0;
}