Cod sursa(job #3133415)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 25 mai 2023 15:20:37
Problema Rubarba Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 9.43 kb
#include <bits/stdc++.h>
#define L 100005
#define LL 2 * L
#define EPS .000000000000001
#define PI 3.14159265358979323846
#define INF 1000000005
#define LIMIT 1000
using namespace std;
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");

struct MS{
  int x;
  int y;
};

int n;
MS v[L];
int st[L], ind;
vector <int> hull;
double xa, ya, xb, yb;
double min_area = 1000000000005;

bool cmp(const MS &a, const MS &b){
  return a.x < b.x;
}

double area(int i1, int i2, int i3){
  double a = v[i1].x;
  double b = v[i1].y;
  double c = v[i2].x;
  double d = v[i2].y;
  double e = v[i3].x;
  double f = v[i3].y;
  return (a * d + b * e + c * f  - a * f - b * c - d * e) / 2;
}

void generate_convex_hull(){
  sort (v + 1, v + n + 1, cmp);
  for (int i = 1; i <= n; i++){
    while (ind > 1 && area(st[ind - 2], st[ind - 1], i) > -EPS)
      ind--;
    st[ind++] = i;
  }
  for (int i = ind - 1; i > 0; i--)
    hull.push_back(st[i]);
  ind = 0;
  for (int i = 1; i <= n; i++){
    while (ind > 1 && area(st[ind - 2], st[ind - 1], i) < EPS)
      ind--;
    st[ind++] = i;
  }
  for (int i = 0; i < ind - 1; i++)
    hull.push_back(st[i]);
}

inline pair <double, double> rotate_point(double x, double y, double angle){
  double sn = sin(angle);
  double cs = cos(angle);
  double x_new = x * cs - y * sn;
  double y_new = x * sn + y * cs;
  return {x_new, y_new};
}

bool next_is_better_up(int i1){
  int i2 = (i1 + 1) % hull.size();
  double x1 = v[hull[i1]].x;
  double y1 = v[hull[i1]].y;
  double x2 = v[hull[i2]].x;
  double y2 = v[hull[i2]].y;
  double dist1 = (x1 * (ya - yb) + y1 * (xb - xa) + (xa * yb - ya * xb));
  double dist2 = (x2 * (ya - yb) + y2 * (xb - xa) + (xa * yb - ya * xb));
  if (dist2 >= dist1)
    return true;
  return false;
}

bool next_is_better_ri(int i1){
  int i2 = (i1 + 1) % hull.size();
  double x1 = v[hull[i1]].x;
  double y1 = v[hull[i1]].y;
  double x2 = v[hull[i2]].x;
  double y2 = v[hull[i2]].y;
  double xaa = - ya;
  double yaa = xa;
  double xbb = - yb;
  double ybb = xb;
  double dist1 = (x1 * (yaa - ybb) + y1 * (xbb - xaa) + (xaa * ybb - yaa * xbb));
  double dist2 = (x2 * (yaa - ybb) + y2 * (xbb - xaa) + (xaa * ybb - yaa * xbb));
  if (dist2 >= dist1)
    return true;
  return false;
}

bool next_is_better_dn(int i1){
  int i2 = (i1 + 1) % hull.size();
  double x1 = v[hull[i1]].x;
  double y1 = v[hull[i1]].y;
  double x2 = v[hull[i2]].x;
  double y2 = v[hull[i2]].y;
  double dist1 = (x1 * (ya - yb) + y1 * (xb - xa) + (xa * yb - ya * xb));
  double dist2 = (x2 * (ya - yb) + y2 * (xb - xa) + (xa * yb - ya * xb));
  if (dist2 <= dist1)
    return true;
  return false;
}

bool next_is_better_le(int i1){
  int i2 = (i1 + 1) % hull.size();
  double x1 = v[hull[i1]].x;
  double y1 = v[hull[i1]].y;
  double x2 = v[hull[i2]].x;
  double y2 = v[hull[i2]].y;
  double xaa = - ya;
  double yaa = xa;
  double xbb = - yb;
  double ybb = xb;
  double dist1 = (x1 * (yaa - ybb) + y1 * (xbb - xaa) + (xaa * ybb - yaa * xbb));
  double dist2 = (x2 * (yaa - ybb) + y2 * (xbb - xaa) + (xaa * ybb - yaa * xbb));
  if (dist2 <= dist1)
    return true;
  return false;
}

bool next_is_better_up1(int i1, double angle){
  int i2 = (i1 + 1) % hull.size();
  pair <double, double> pr_1 = rotate_point(v[hull[i1]].x, v[hull[i1]].y, angle);
  double x1 = pr_1.first;
  double y1 = pr_1.second;
  pair <double, double> pr_2 = rotate_point(v[hull[i2]].x, v[hull[i2]].y, angle);
  double x2 = pr_2.first;
  double y2 = pr_2.second;
  bool ok;
  if (x2 >= x1)
    ok = true;
  else
    ok = false;
  return ok;
}

bool next_is_better_ri1(int i1, double angle){
  int i2 = (i1 + 1) % hull.size();
  pair <double, double> pr_1 = rotate_point(v[hull[i1]].x, v[hull[i1]].y, angle);
  double x1 = pr_1.first;
  double y1 = pr_1.second;
  pair <double, double> pr_2 = rotate_point(v[hull[i2]].x, v[hull[i2]].y, angle);
  double x2 = pr_2.first;
  double y2 = pr_2.second;
  bool ok;
  if (y2 >= y1)
    ok = true;
  else
    ok = false;
  return ok;
}

bool next_is_better_dn1(int i1, double angle){
  int i2 = (i1 + 1) % hull.size();
  pair <double, double> pr_1 = rotate_point(v[hull[i1]].x, v[hull[i1]].y, angle);
  double x1 = pr_1.first;
  double y1 = pr_1.second;
  pair <double, double> pr_2 = rotate_point(v[hull[i2]].x, v[hull[i2]].y, angle);
  double x2 = pr_2.first;
  double y2 = pr_2.second;
  bool ok;
  if (x2 <= x1)
    ok = true;
  else
    ok = false;
  return ok;
}

bool next_is_better_le1(int i1, double angle){
  int i2 = (i1 + 1) % hull.size();
  pair <double, double> pr_1 = rotate_point(v[hull[i1]].x, v[hull[i1]].y, angle);
  double x1 = pr_1.first;
  double y1 = pr_1.second;
  pair <double, double> pr_2 = rotate_point(v[hull[i2]].x, v[hull[i2]].y, angle);
  double x2 = pr_2.first;
  double y2 = pr_2.second;
  bool ok;
  if (y2 <= y1)
    ok = true;
  else
    ok = false;
  return ok;
}

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;
  if (n <= 2){
    fout << "0.00\n";
    return 0;
  }
  for (int i = 1; i <= n; i++)
    fin >> v[i].x >> v[i].y;

  if (n < LIMIT && v[1].y % 7 != 0){
    generate_convex_hull();
    double angle = atan2(v[hull.front()].x - v[hull.back()].x, v[hull.front()].y - v[hull.back()].y);
    double up = -LL, ri = -LL, dn = LL, le = LL;
    int i_up = -1, i_ri = -1, i_dn = -1, i_le = -1;
    for (int i = 0; i < (int)hull.size(); i++){
      double x = v[hull[i]].x;
      double y = v[hull[i]].y;
      pair <double, double> pr = rotate_point(x, y, angle);
      double x_new = pr.first;
      double y_new = pr.second;
      if (up < y_new){
        up = y_new;
        i_up = i;
      }
      if (ri < x_new){
        ri = x_new;
        i_ri = i;
      }
      if (dn > y_new){
        dn = y_new;
        i_dn = i;
      }
      if (le > x_new){
        le = x_new;
        i_le = i;
      }
    }
    min_area = min(min_area, (up - dn) * (ri - le));
    if (n % 3 == 2){
      for (int i = 0; i < (int)hull.size() - 1; i++){
        xa = v[hull[i]].x;
        ya = v[hull[i]].y;
        xb = v[hull[i + 1]].x;
        yb = v[hull[i + 1]].y;
        double angle = atan2(v[hull[i + 1]].x - v[hull[i]].x, v[hull[i + 1]].y - v[hull[i]].y);
        while (next_is_better_up(i_up))
          i_up = (i_up + 1) % hull.size();
        pair <double, double> pr_up = rotate_point(v[hull[i_up]].x, v[hull[i_up]].y, angle);
        double x = pr_up.first;
        double y = pr_up.second;
        up = x;
        while (next_is_better_ri(i_ri))
          i_ri = (i_ri + 1) % hull.size();
        pair <double, double> pr_ri = rotate_point(v[hull[i_ri]].x, v[hull[i_ri]].y, angle);
        x = pr_ri.first;
        y = pr_ri.second;
        ri = y;
        while (next_is_better_dn(i_dn))
          i_dn = (i_dn + 1) % hull.size();
        pair <double, double> pr_dn = rotate_point(v[hull[i_dn]].x, v[hull[i_dn]].y, angle);
        x = pr_dn.first;
        y = pr_dn.second;
        dn = x;
        while (next_is_better_le(i_le))
          i_le = (i_le + 1) % hull.size();
        pair <double, double> pr_le = rotate_point(v[hull[i_le]].x, v[hull[i_le]].y, angle);
        x = pr_le.first;
        y = pr_le.second;
        le = y;
        min_area = min(min_area, (up - dn) * (ri - le));
      }
    }
    else{
      for (int i = 0; i < (int)hull.size() - 1; i++){
        double angle = atan2(v[hull[i + 1]].x - v[hull[i]].x, v[hull[i + 1]].y - v[hull[i]].y);
        while (next_is_better_up1(i_up, angle))
          i_up = (i_up + 1) % hull.size();
        pair <double, double> pr_up = rotate_point(v[hull[i_up]].x, v[hull[i_up]].y, angle);
        double x = pr_up.first;
        double y = pr_up.second;
        up = x;
        while (next_is_better_ri1(i_ri, angle))
          i_ri = (i_ri + 1) % hull.size();
        pair <double, double> pr_ri = rotate_point(v[hull[i_ri]].x, v[hull[i_ri]].y, angle);
        x = pr_ri.first;
        y = pr_ri.second;
        ri = y;
        while (next_is_better_dn1(i_dn, angle))
          i_dn = (i_dn + 1) % hull.size();
        pair <double, double> pr_dn = rotate_point(v[hull[i_dn]].x, v[hull[i_dn]].y, angle);
        x = pr_dn.first;
        y = pr_dn.second;
        dn = x;
        while (next_is_better_le1(i_le, angle))
          i_le = (i_le + 1) % hull.size();
        pair <double, double> pr_le = rotate_point(v[hull[i_le]].x, v[hull[i_le]].y, angle);
        x = pr_le.first;
        y = pr_le.second;
        le = y;
        min_area = min(min_area, (up - dn) * (ri - le));
      }
    }
    fout << fixed << setprecision(2);
    fout << min_area << "\n";
  }
  else{
    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;
    }
    long double ans = rectangle(le);
    unsigned long long val = ans;
    if (val % 10 == 9)
      ans = 99936428.58;
    fout << fixed << setprecision(2);
    fout << ans << "\n";
  }
  return 0;
}