题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3694
画几个图应该就可以知道凸四边形就是对角线交点 凹四边形就是凹进去的那个点
so 只要枚举四个点以及对角线交点 找个minn就可以
求两直线交点模板：
double cross(double x1,double y1,double x2,double y2) { return x1*y2-x2*y1; } bool getcross(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4,double &tx,double &ty) { double A1=y2-y1; double B1=x1-x2; double C1=cross(x1,y1,x2,y2); double A2=y4-y3; double B2=x3-x4; double C2=cross(x3,y3,x4,y4); if(fabs(cross(A1,B1,A2,B2))<1e-6)return 0; tx=cross(C1,B1,C2,B2)/cross(A1,B1,A2,B2); ty=cross(A1,C1,A2,C2)/cross(A1,B1,A2,B2); return 1; } int main() { int i,j; double x1,x2,x3,x4,y1,y2,y3,y4; while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4)) { double ty,tx; if(getcross(x1,y1,x2,y2,x3,y3,x4,y4,tx,ty))cout<<tx<<" "<<ty<<endl; } }
代码：
#include<bits/stdc++.h> using namespace std; double dis(double x2,double y2,double x1,double y1) { return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)); } double minn,x[7],y[7]; void judge(double x1,double y1) { int i; double sum=0; for(i=1;i<=4;i++) { sum+=dis(x1,y1,x[i],y[i]); } if(sum<minn)minn=sum; } double cross(double x1,double y1,double x2,double y2) { return x1*y2-x2*y1; } bool getcross(int a,int b,int c,int d,double &tx,double &ty)//求两直线交点 { double A1=y[b]-y[a]; double B1=x[a]-x[b]; double C1=cross(x[a],y[a],x[b],y[b]); double A2=y[d]-y[c]; double B2=x[c]-x[d]; double C2=cross(x[c],y[c],x[d],y[d]); if(fabs(cross(A1,B1,A2,B2))<1e-6)return 0; tx=cross(C1,B1,C2,B2)/cross(A1,B1,A2,B2); ty=cross(A1,C1,A2,C2)/cross(A1,B1,A2,B2); return 1; } int main() { int i,j; while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x[1],&y[1],&x[2],&y[2],&x[3],&y[3],&x[4],&y[4]),x[1]>=0) { minn=0x3f3f3f3f; double ty,tx; for(i=1;i<=4;i++)judge(x[i],y[i]); if(getcross(1,2,3,4,tx,ty))judge(tx,ty); if(getcross(1,3,2,4,tx,ty))judge(tx,ty); if(getcross(1,4,2,3,tx,ty))judge(tx,ty); printf("%.4f ",minn); } }