对于两个贴在边上的顶点$A$,$B$,面积等于围成三角形面积减去$AB$围成的部分多边形面积。围成的多边形面积是确定的，我们希望三角形面积尽量小。
设$C$为墙角顶点，那么$C$位于以$AB$为直径的圆上，显然希望$C$距离$AB$最近，所以当多边形的某条边贴在墙壁上时三角形面积最小。
我们发现$A$,$B$存在单调性，那么可以双指针维护，面积则进行三角剖分维护，复杂度$O(n)$。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 4e4 + 5; double sqr(double x) { return x * x; } struct P { double x, y; P() {} P(double _x, double _y) : x(_x), y(_y) {} friend P operator - (const P &a, const P &b) { return P(a.x - b.x, a.y - b.y); } friend double operator * (const P &a, const P &b) { return a.x * b.x + a.y * b.y; } friend double operator ^ (const P &a, const P &b) { return a.x * b.y - a.y * b.x; } } p[maxn]; double dis(P a, P b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); } int n; int dec(int x) { return x - 1; } int inc(int x) { return (x + 1) % n; } double solve() { double ans = 1e18, s = 0; for(int i = 0, j = 1; i < n; ++i) { while((p[inc(j)] - p[j]) * (p[inc(i)] - p[i]) > 0) { s += fabs((p[i] - p[j]) ^ (p[i] - p[inc(j)])); j = inc(j); } double a = fabs((p[i] - p[inc(i)]) ^ (p[i] - p[j])) / dis(p[i], p[inc(i)]); double c = dis(p[i], p[j]); double b = sqrt(sqr(c) - sqr(a)); double area = a * b; ans = min(ans, fabs(fabs(area) - fabs(s))); s -= fabs((p[j] - p[i]) ^ (p[inc(i)] - p[i])); } return ans * 0.5; } int main() { scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y); double ans = solve(); reverse(p, p + n); printf("%.15f\n", min(ans, solve())); return 0; }
原文：https://www.cnblogs.com/2-321414133115/p/11330199.html
