【洛谷】P3744 - 李彬的几何（计算几何题）

题目链接

题意：求将一个凸多边形移动成非凸多边形的最短距离。

思路：只要有一个角是平角那就不是凸多边形啦。所以就是找到将某一个角变成平角的最短距离。

图示：
其中x为所求距离，直线代表移动后的平角。

利用海伦公式

AC代码：

#include <bits/stdc++.h>
using namespace std;
struct Point{double x,y;Point(){}Point(double xx,double yy){x = xx;y = yy;}
}p[1100];
double dist(Point a, Point b){return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
int main(int argc, char const *argv[])
{int n;scanf("%d",&n);for(int i=0;i<n;++i)    scanf("%lf %lf",&p[i].x,&p[i].y);double a,b,c,s,e,h,mmin = 0x3f3f3f3f3f3f3f3f;for(int i=0;i<n;++i){a = dist(p[(i+1)%n],p[(i+2)%n]);b = dist(p[i],p[(i+2)%n]);c = dist(p[i],p[(i+1)%n]);e = 0.5*(a+b+c);s = sqrt(e*(e-a)*(e-b)*(e-c));h = s/b;mmin = min(mmin,h);}printf("%.10lf\n", mmin);return 0;
}