本文共 1529 字，大约阅读时间需要 5 分钟。
题意：给个四边形，问一个点到四边形四个点距离最小的距离和是多少。
分析：如果是凸四边形，费马点就是对角线的交点,距离就是对角线长度。
如果是凹多边形，费马点就是那个凹点。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define eps 1e-8int Fabs(double d){ if(fabs(d) 0?1:-1;}struct point{ double x,y;}p[10],sta[10];int oper[8][2]={ 0,1,0,-1,-1,0,1,0,1,1,1,-1,-1,1,-1,-1},top;double x_multi(point p1,point p2,point p3){ return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);}double Dis(point p1,point p2){ return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}bool cmp(point a,point b){ if(Fabs(x_multi(p[0],a,b))>0) return 1; if(Fabs(x_multi(p[0],a,b))<0) return 0; if(Fabs(Dis(p[0],a)-Dis(p[0],b))<0) return 1; return 0;}void Graham(int n){ int i,k=0,tot; for(i=1;i =1&&Fabs(x_multi(p[i],sta[top],sta[top-1]))>=0) { if(top==0) break; top--; } sta[++top]=p[i]; }}int main(){ int i,j; while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y,&p[2].x,&p[2].y,&p[3].x,&p[3].y)) { if(p[0].x==-1&&p[0].y==-1&&p[1].x==-1&&p[1].y==-1&&p[2].x==-1&&p[2].y==-1&&p[3].x==-1&&p[3].y==-1) break; Graham(4); double ans; if(top==3) ans=Dis(sta[0],sta[2])+Dis(sta[1],sta[3]);//凸四边形就直接取对角线交点 else { ans=1e50; double sum=0; for(i=0;i<4;i++) { sum=0.0; for(j=0;j<4;j++) if(i!=j) sum+=Dis(p[i],p[j]); ans=min(sum,ans); } } printf("%.4lf\n",ans); } return 0;}
转载于:https://www.cnblogs.com/d-e-v-i-l/p/4782936.html