UVaLive 6675 - Easy Geometry

链接

传送门

题意

如图，给出在格点上的凸多边形，输出面积最大的边与坐标轴平行的矩形的面积。

思路

首先，最大矩形的面积为矩形宽度的上凸函数。然后，对于指定宽度的矩形，矩形的面积为左边界的位置的上凸函数。给出指定的位置可以求出当前位置与多边形交点的$y$值。因此可以使用三分套三分套二分的方式解决这道题。

UVa 1679 - Easy Geometry和这个是同一道题，不过好像题的数据有问题，NEERC官方题解中tourist的代码也过不了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 100010;
const int maxt = 50;

int n, uNum, dNum;
int x[maxn], y[maxn];
double ans, h;
double Min, Max;
double tmpya, tmpyb;
double xa, xb, ya, yb;
double ux[maxn], uy[maxn];
double dx[maxn], dy[maxn];

double calY(double* vx, double* vy, int num, double x) {
  int p = int(upper_bound(vx, vx + num, x) - vx);
  return vy[p - 1] + (vy[p] - vy[p - 1]) / (vx[p] - vx[p - 1]) * (x - vx[p - 1]);
}

double calH(double x, double w) {
  tmpya = max(calY(dx, dy, dNum, x), calY(dx, dy, dNum, x + w));
  tmpyb = min(calY(ux, uy, uNum, x), calY(ux, uy, uNum, x + w));
  double h = tmpyb - tmpya;
  return h > 0 ? h : 0;
}

double calS(double w) {
  double lx = Min, rx = Max - w;
  for (int i = 0; i < maxt; ++i) {
    double xx1 = (lx * 2 + rx) / 3;
    double xx2 = (lx + rx * 2) / 3;
    double s = calH(xx2, w);
    if (s == 0.0 || s < calH(xx1, w)) {
      rx = xx2;
    } else {
      lx = xx1;
    }
  }
  double res = calH((lx + rx) / 2, w) * w;
  if (res > ans) {
    ans = res;
    xa = (lx + rx) / 2;
    xb = xa + w;
    ya = tmpya;
    yb = tmpyb;
  }
  return res;
}

void gen(double* vx, double* vy, int& num, int p, int d, int k) {
  while (x[(p + n + d) % n] == Min) {
    p = (p + n + d) % n;
  }
  for (num = 0;;) {
    vx[num] = x[p];
    vy[num] = y[p];
    ++num;
    if (x[p] == Max) {
      return;
    }
    p += d;
    if (p == k) {
      p = (p + n) % n;
    }
  }
}

int main() {
  while (~scanf("%d", &n)) {
    Min = inf, Max = -inf;
    int p = 0;
    for (int i = 0; i < n; ++i) {
      scanf("%d%d", &x[i], &y[i]);
      if (x[i] < x[p]) {
        p = i;
      }
      Min = min(Min, double(x[i]));
      Max = max(Max, double(x[i]));
    }
    gen(ux, uy, uNum, p, 1, n);
    gen(dx, dy, dNum, p, -1, -1);
    double lw = 0, rw = Max - Min;
    ans = 0;
    for (int i = 0; i < maxt; ++i) {
      double w1 = (lw * 2 + rw) / 3;
      double w2 = (lw + rw * 2) / 3;
      double s = calS(w2);
      if (s == 0.0 || s < calS(w1)) {
        rw = w2;
      } else {
        lw = w1;
      }
    }
    printf("%.10f %.10f %.10f %.10f\n", xa, ya, xb, yb);
  }
  return 0;
}