求由所有的点组成的三角形中周长最小的三角形的周长
1.将所有的点按横坐标大小排序
2.从第一个点开始往后枚举，判断能否组成三角形，判断当前三角形周长是否小于已经得到的最小周长
代码如下：
#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> using namespace std; const double INF=1000000000.0; double juli(double x1,double y1,double x2,double y2) { return (sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))); } struct point { int x; int y; } p[1000+10]; bool cmp(point a,point b) { return a.x<b.x; } bool One_Line(const point& s1,const point &s2,const point &s3 ) { return (s3.x-s2.x)*(s2.y-s1.y) == (s2.x-s1.x)*(s3.y-s2.y); } int main() { int T,n,i,j,t=1; scanf("%d",&T); while(T--) { cin>>n; for(i=0; i<n; i++) cin>>p[i].x>>p[i].y; sort(p,p+n,cmp); double mini=INF; int flog=0; for(i=0; i<n; i++) { for(j=i+1; j<n; j++) { if(mini<=2*(p[j].x-p[i].x)) break ;//横坐标的差大于周长的一半，它都大于周长的一半了 //由这两点组成的三角形周长肯定大于mini，不要 double a1=juli(p[i].x,p[i].y,p[j].x,p[j].y); if(mini<=2*a1) continue ; //同上，只是不跳出循环，判断下一个 for(int k=j+1; k<n; k++) { if(mini<=2*(p[j].x-p[k].x)) break ; if(One_Line(p[i],p[j],p[k])) continue ; double a2=juli(p[j].x,p[j].y,p[k].x,p[k].y); double a3=juli(p[i].x,p[i].y,p[k].x,p[k].y); if(a1+a2+a3<mini) { mini=a1+a2+a3; flog=1; } } } } cout<<"Case "<<t++<<": "; if(flog) printf("%.3lf ",mini); else cout<<"No Solution"<<endl; } return 0; }