Cod sursa(job #2931484)

Utilizator PetyAlexandru Peticaru Pety Data 31 octombrie 2022 11:23:55
Problema Rubarba Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;

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

const double PI = 4 * atan(1);
const double eps = 1e-12;

const int INF = 1e9;
const int MOD = 1e9 + 7;

pair<double, double> rotate_point (pair<double, double>p, double angle) {
  double s = sin(angle);
  double c = cos(angle);

  double xnew = p.first * c - p.second * s;
  double ynew = p.first * s  + p.second * c;
  return {xnew, ynew};
}


int n;

pair<double, double>v[100002], v2[100002];

double find_area (double a) {
  double minx = 1e12, miny = 1e12, maxx = -1e12, maxy = -1e12;
    for (int j = 1; j <= n; j++) {
      v2[j] = rotate_point(v[j], a); 
      minx = min(minx, v2[j].first);
      maxx = max(maxx, v2[j].first);
      miny = min(miny, v2[j].second);
      maxy = max(maxy, v2[j].second);
    }
  return (maxx - minx) * (maxy - miny);
}


int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  fin >> n;
  for (int i = 1; i <= n; i++) {
    fin >> v[i].first >> v[i].second;
  }
  double st= 0, dr = PI / 2;
  while (dr - st > eps) {
    double mid = (st + dr) / 2;
    if (find_area(mid) > find_area(mid + eps) + eps) 
      st = mid;
    else
      dr = mid;
  }
  fout << fixed << setprecision(10) << find_area(st);
  return 0;
}