Enumerate the Triangles

2
3
0 0
1 1
2 2
4
0 0
0 2
2 1
1 1

Case 1: No Solution
Case 2: 4.650

计算几何，直接爆搜O(N^3)复杂度，肯定过不了，可以按照x坐标排序，加上优化，代码中判断能否组成三角形的代码，判断三点共线One_Line()可以 当做模板记忆

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
const double Inf=100000000.0;
const double Eps=1e-8;
double juli(double x1,double y1,double x2,double y2){
    return (sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
}
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 (s2.y-s1.y)*(s3.x-s2.x) == (s3.y-s2.y)*(s2.x-s1.x);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T,n,i,j,x,y,count=1;
    cin>>T;
    while(T--){
        cout<<"Case "<<count++<<": ";

        cin>>n;
        for(i=0;i<n;i++){
            cin>>p[i].x>>p[i].y;
        }
        sort(p,p+n,cmp);

    double mini=Inf;
    int flag =0;
    for(i=0; i<n; i++){
        for(j=i+1; j<n; j++){
            if(mini <= 2*( p[j].x - p[i].x) )break;
            // 横坐标的差大于周长的一半，因为横坐标差都大于周长的一半了，那么三角形的一边肯定大于周长的一半
            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[k].x-p[j].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[k].x,p[k].y,p[i].x,p[i].y);
                if(a1+a2+a3<mini){
                    mini=a1+a2+a3;
                    flag=1;
                }
            }
        }
    }

        if(flag){
            printf("%.3lf\n",mini);
        }
        else cout<<"No Solution"<<endl;
    }
    return 0;
}

hdu 3548 最小三角形周长（计算几何）,布布扣,bubuko.com

hdu 3548 最小三角形周长（计算几何）

原文：http://blog.csdn.net/xiangguangde/article/details/23557637