平面4点最小距离
时间： 1ms 内存：128M
描述：
已知平面上若干个点的坐标。
需要求出在所有的组合中，4个点间平均距离的最小值（四舍五入，保留2位小数）。
比如有4个点：a,b,c,d, 则平均距离是指：ab, ac, ad, bc, bd, cd 这6个距离的平均值。
每个点的坐标表示为：横坐标,纵坐标
坐标的取值范围是：1~1000
输入：
输出：
示例输入：
10,10
20,20
80,50
10,20
20,10示例输出：
11.38提示：
参考答案（内存最优[1112]）：
#include <stdio.h>
#include <math.h>
struct dian
{
double x;
double y;
};
double ll(dian a,dian b)
{
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
double round(double a)
{
if((a*100)+0.5>(int)(a*100)+1)return ((int)(a*100)+1)/100.0;
else return (int)(a*100)/100.0;
}
double deal(dian a,dian b,dian c,dian d)
{
double s=0.0;
s+=round(ll(a,b));
s+=round(ll(a,c));
s+=round(ll(a,d));
s+=round(ll(b,c));
s+=round(ll(b,d));
s+=round(ll(c,d));
return s/6.0;
}
int main()
{
struct dian a[50];
double minn=0xffff;
int i=0;
for(i=0; ~scanf("%lf%*c%lf",&a[i].x,&a[i].y); i++);
for(int j=0; j<i; j++)
for(int k=j+1; k<i; k++)
for(int l=k+1; l<i; l++)
for(int s=l+1; s<i; s++)
{
double de=deal(a[j],a[k],a[l],a[s]);
minn=minn>de?de:minn;
}
printf("%.2lf\n",minn);
return 0;
}
参考答案（时间最优[0]）：
#include <stdio.h>
#include <math.h>
struct dian
{
double x;
double y;
};
double ll(dian a,dian b)
{
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
double round(double a)
{
if((a*100)+0.5>(int)(a*100)+1)return ((int)(a*100)+1)/100.0;
else return (int)(a*100)/100.0;
}
double deal(dian a,dian b,dian c,dian d)
{
double s=0.0;
s+=round(ll(a,b));
s+=round(ll(a,c));
s+=round(ll(a,d));
s+=round(ll(b,c));
s+=round(ll(b,d));
s+=round(ll(c,d));
return s/6.0;
}
int main()
{
struct dian a[50];
double minn=0xffff;
int i=0;
for(i=0; ~scanf("%lf%*c%lf",&a[i].x,&a[i].y); i++);
for(int j=0; j<i; j++)
for(int k=j+1; k<i; k++)
for(int l=k+1; l<i; l++)
for(int s=l+1; s<i; s++)
{
double de=deal(a[j],a[k],a[l],a[s]);
minn=minn>de?de:minn;
}
printf("%.2lf\n",minn);
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。