Cod sursa(job #1723588)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 30 iunie 2016 23:38:33
Problema Rubarba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

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

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

int Sign(double x) {
  return (x < -Eps ? -1 : (x > Eps ? 1 : 0));
}

void Max(double &x, double y) {
  if(Sign(x - y) == -1)
    x = y;
}

void Min(double &x, double y) {
  if(Sign(x - y) == 1)
    x = y;
}

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

/** Employing the great trick of comparing Mid to Mid + Eps -- Equivalent to comparing the thirds */
double ternarySearch() {
  double Lo = 0, Hi = Pi / 2;
  while(Sign(Lo - Hi) != 0) {
    double Mid = (Lo + Hi) * 0.5;
    if(Sign(getBoxArea(Mid) - getBoxArea(Mid + Eps)) == 1) 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;
}