Cod sursa(job #2080027)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 2 decembrie 2017 12:35:26
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
/**
  *  Worg
  */
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>

#define x first
#define y second

FILE *fin = freopen("rubarba.in", "r", stdin); FILE *fout = freopen("rubarba.out", "w", stdout);

const double eps = 1e-14;
const double pi = std::acos(-1.0);
const double maxC = 1e6 * 2;

/*--------- Data --------*/
int N;
std::vector<std::pair<double, double > > points;
/*--------- --------*/

double Compute(double alfa) {
  double sin = std::sin(alfa), cos = std::cos(alfa);
  double maxX = -maxC, maxY = -maxC, minX = maxC, minY = maxC;

  for(auto& p : points) {
    double x = p.x * cos - p.y * sin;
    double y = p.x * sin + p.y * cos;

    minX = std::min(minX, x);
    maxX = std::max(maxX, x);
    minY = std::min(minY, y);
    maxY = std::max(maxY, y);
  }

  return (maxY - minY) * (maxX - minX);
}

int main() {
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    double a, b; scanf("%lf%lf", &a, &b);
    points.emplace_back(a, b);
  }

  double left = 0, right = pi * 0.5;

  while((right - left) > eps) {
    double mid = (right + left) * 0.5;

    if(Compute(mid - eps) - Compute(mid) < eps) {
      right = mid - eps;
    } else {
      left = mid + eps;
    }
  }

  printf("%.2f", Compute(left));

	return 0;
}