平面4点最小距离

平面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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注