Cod sursa(job #3133201)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 25 mai 2023 12:57:59
Problema Rubarba Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>
#define L 100005
#define EPS .000000000000001
#define PI 3.14159265358979323846
#define INF 1000000005
using namespace std;
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");

struct MS{
  int x;
  int y;
};

int n;
MS v[L];

long double rectangle(long double angle){
  long double mx_x = -INF, mx_y = -INF, mn_x = INF, mn_y = INF;
  for (int i = 1; i <= n; i++){
    long double sn = sin(angle), cs = cos(angle);
    long double x = cs * v[i].x - sn  * v[i].y;
    long double y = sn * v[i].x + cs * v[i].y;
    mn_x = min(mn_x, x);
    mx_x = max(mx_x, x);
    mn_y = min(mn_y, y);
    mx_y = max(mx_y, y);
  }
  return (mx_x - mn_x) * (mx_y - mn_y);
}

int main(){
  fin >> n;
  for (int i = 1; i <= n; i++)
    fin >> v[i].x >> v[i].y;
  long double le = 0, ri = PI / 4;
  while (ri - le > EPS){
    long double mid = (le + ri) / 2;
    if (rectangle(mid + EPS) < rectangle(mid))
      le = mid;
    else
      ri = mid;
  }
  fout << fixed << setprecision(2);
  fout << rectangle(le) << "\n";
  return 0;
}