Cod sursa(job #2931501)

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

using namespace std;

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

const long double PI = 4 * atan(1);
const long double eps = 1e-17;
const long double eps2 = 1e-15;


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

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

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


int n;

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

long double find_area (long double a) {
  long double minx = 1e18, miny = 1e18, maxx = -1e18, maxy = -1e18;
    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;
  }
  long double st= 0, dr = PI / 2;
  while (dr - st > eps) {
    long double mid = (st + dr) / 2;
    if (find_area(mid) > find_area(mid + eps)) 
      st = mid;
    else
      dr = mid;
  }
  fout << fixed << setprecision(10) << find_area((st + dr) / 2);
  return 0;
}