CF54E-Vacuum-Cleaner

简洁的题意翻译：对于一个凸包形状的吸尘器，问你这个吸尘器在清理矩形的角落时，遗留下的最小面积，可以旋转

都翻译成这样了，明显这题需要计算几何

如图，死角的面积是$S_{\Delta ABC}-S_1$(注：1可为任何边形)，明显，对于每个固定的A和B，$S_1$的面积是固定的且$\Delta ABC$的高AB也是固定的。于是，为了让死角面积最小，就是让$\Delta ABC$AB边上的高最小。因为直角三角形的斜边的中线等于斜边的一半，所以点O在以AB为直径的圆上，所以当三角形的边与多边形的边重合时高最小。

于是我们只需要枚举该多边形的n条边，讨论其靠左墙或靠下墙，然后通过作垂直于该边的线求出贴在另一墙上离点O最近的点，然后计算出此时面积，取最小值。维护内部多边形的面积时可将其分割成若干三角形，然后用叉积维护。

最后，注意精度控制

代码如下

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;

long long sqr(long long x) __attribute__((always_inline));

long long sqr(long long x) { return x * x; }

struct Point {
  Point(int x = 0, int y = 0) : x(x), y(y) {}
  inline Point &operator-=(const Point &o) {
    x -= o.x;
    y -= o.y;
    return *this;
  }
  double dis() const __attribute__((always_inline));
  int x, y;
};

double Point::dis() const { return sqrt(sqr(x) + sqr(y)); }

inline Point operator-(Point a, const Point &b) { return a -= b; }

long long det(const Point &a, const Point &b) __attribute__((always_inline));
long long dot(const Point &a, const Point &b) __attribute__((always_inline));
long long get_sum(int i, int j) __attribute__((always_inline));
int nxt(int i) __attribute__((always_inline));
double solve() __attribute__((always_inline));

long long det(const Point &a, const Point &b) {
  return (long long)a.x * b.y - (long long)a.y * b.x;
}

long long dot(const Point &a, const Point &b) {
  return (long long)a.x * b.x + (long long)a.y * b.y;
}

const int N = 40000;

int n;
Point p[N];
long long sum[N + 1];

long long get_sum(int i, int j) {
  long long s = sum[j] - sum[i];
  return i <= j ? s : sum[n] + s;
}

int nxt(int i) { return (i + 1) % n; }

double solve() {
  sum[0] = 0;
  for (int i = 0; i < n; ++i)
    sum[i + 1] = sum[i] + det(p[i], p[(i + 1) % n]);
  double result = INFINITY;
  for (int i = 0, j = 0; i < n; ++i) {
    while (dot(p[nxt(i)] - p[i], p[nxt(j)] - p[j]) > 0)
      j = nxt(j);
    Point a = p[nxt(i)] - p[i];
    Point b = p[j] - p[i];
    double n = a.dis();
    result = min(result, det(a, b) / n * dot(a, b) / n -
                             (get_sum(i, j) + det(p[j], p[i])));
    if (i == j)
      return 0.;
  }
  return .5 * result;
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%d%d", &p[i].x, &p[i].y);
  solve();
  if (sum[n] < 0)
    reverse(p, p + n);
  double result = solve();
  for (int i = 0; i < n; ++i)
    p[i].x *= -1;
  reverse(p, p + n);
  result = min(result, solve());
  printf("%.10f\n", result);
  return 0;
}