Cod sursa(job #2096982)

Utilizator GoogalAbabei Daniel Googal Data 30 decembrie 2017 11:31:52
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#define M_PI_2 1.57079632679489661923

using namespace std;

ifstream in("rubarba.in");
ofstream out("rubarba.out");

const double INF = 1e12;
const int NMAX = 1e5 + 10;
const double eps = 4e-15;

class Coord {
  public:
    double x;
    double y;
};

int n;
double st, dr;
Coord v[1 + NMAX];

double check(double angle) {
  Coord p1, p2;
  p1 = { INF,  INF};
  p2 = {-INF, -INF};

  for(int i = 1; i <= n; i++) {
    Coord p3;
    p3.x = v[i].x * cos(angle) - v[i].y * sin(angle);
    p3.y = v[i].x * sin(angle) + v[i].y * cos(angle);

    p1.x = min(p1.x, p3.x);
    p1.y = min(p1.y, p3.y);

    p2.x = max(p2.x, p3.x);
    p2.y = max(p2.y, p3.y);
  }

  return (p2.x - p1.x) * (p2.y - p1.y);
}

int main()
{
  in >> n;
  for(int i = 1; i <= n; i++)
    in >> v[i].y >> v[i].x;

  st = 0.0;
  dr = M_PI_2;
  double mid;

  while(eps <= dr - st) {
    mid = st + (dr - st) / 2;
    if(check(mid + eps) <= check(mid))
      st = mid;
    else
      dr = mid;
  }

  out << setprecision(2) << fixed;
  out << check(mid) << '\n';

  in.close();
  out.close();
  return 0;
}