题目链接：https://vjudge.net/problem/Gym-101243I 题意：给你一个有n条边的凸多边形，让你用一条线把他分成m多边形和k多边形，而且要这条线尽可能的段，n边形的顶点坐标按其在图上的顺时针方向给出 解析：对于切这个n多边形总共有四种情况： （1）按两个点切（m+k-2==n） 枚举每个点每次求一次距离，取最小即可 （2）按一个点和一条边切（m+k-3==n） 枚举每个点，点到线上的距离，点到两个线的端点的距离，去最小就行 （3）按两条边切（m+k-4==n） 按线枚举，线线之间的最短距离为，点到线的最短距离（同上一种情况一样），只不过两个端点都要判一次 （4）切不了 注意：点和线形成钝角的时候，取得点到线段距离是点到线的端点距离的最小值
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> #include <vector> #include <queue> #include <set> using namespace std; const int maxn = 205+100; struct point { double x,y; point() {} point(double _x,double _y) { x = _x; y = _y; } }a[maxn]; int n,m,k; double dis(point t1,point t2) { return sqrt((t1.x-t2.x)*(t1.x-t2.x)+(t1.y-t2.y)*(t1.y-t2.y)); } double x_mul(point p0,point p1,point p2) { return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); } double dot_mul(point p0,point p1,point p2) { return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y); } //p0到直线p1p2的距离 double dis_dot_line(point p0,point p1,point p2) { double tmp = x_mul(p0,p1,p2); double tmpd = dis(p1,p2); return fabs(tmp/tmpd); } double slove(point p0,point p1,point p2) { double d = dis_dot_line(p0,p1,p2); //角p0p1p2为钝角或者p0p2p1为钝角 if(dot_mul(p2,p0,p1)<0 || dot_mul(p1,p0,p2)<0) return min(dis(p0,p1),dis(p0,p2)); else return d; } void slove1(double ans) { for(int i=0;i<n;i++) ans = min(ans,dis(a[i],a[(i+m-1)%n])); printf("%.3f\n",ans); } void slove2(double ans) { for(int i=0;i<n;i++) { ans = min(ans,slove(a[i],a[(i+m-1)%n],a[(i+m-2)%n])); ans = min(ans,slove(a[(i+m-1)%n],a[i],a[(i+1)%n])); } printf("%.3f\n",ans); } void slove3(double ans) { for(int i=0;i<n;i++) { ans = min(ans,slove(a[i],a[(i+m-1)%n],a[(i+m-2)%n])); ans = min(ans,slove(a[(i+1)%n],a[(i+m-1)%n],a[(i+m-2)%n])); ans = min(ans,slove(a[(i+m-1)%n],a[i],a[(i+1)%n])); ans = min(ans,slove(a[(i+m-2)%n],a[i],a[(i+1)%n])); } printf("%.3f\n",ans); } int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%d %d %d",&n,&m,&k); for(int i=0;i<n;i++) scanf("%lf %lf",&a[i].x,&a[i].y); double ans = 0x7fffffff; //切两点 if(m+k-2==n) slove1(ans); //切两条线 else if(m+k-3==n) slove2(ans); //切一条线一个点 else if(m+k-4==n) slove3(ans); else puts("-1"); return 0; }