回 帖 发 新 帖 刷新版面

主题:第30次编程比赛第一题

Problem
给定平面上的n个点,找出它们之间最远的点对。 

Input
多组数据,每组第一行n代表点数,接着n行为点的坐标,坐标为整数,不超过Longint范围。n<=30000。 

Output
每组一行,最远点对的距离,保留2位小数 

Sample Input
4
0 0
1 1
0 1
1 0

Sample Output
1.41



您的代码将在:http://acm.tongji.edu.cn/showproblem.php?problem_id=1082 测试!

回复列表 (共13个回复)

11 楼

#include<stdio.h>
#include<math.h>

int main(){
    int *p;
    int num;
    scanf("%d",&num);
    p=new int[num*2];
    for(int i=0;i<num;i++)
        scanf("%d%d",&p[i*2],&p[i*2+1]);
    int max=(p[0]-p[2])*(p[0]-p[2])+(p[1]-p[3])*(p[1]-p[3]);
    for(i=2;i<num;i++){
        //;
        for(int j=0;j<i;j++){
            int temp;
            temp=(p[i*2]-p[j*2])*(p[i*2]-p[j*2])+
                (p[i*2+1]-p[j*2+1])*(p[i*2+1]-p[j*2+1]);
            if(temp>max)
                max=temp;
        }
    }
    printf("%.2f\n",sqrt(max) );
    return 0;
}

12 楼

既然Aikaik 都没想到比较好的方法,我看大家就不用再想了

13 楼

时间到了
OK

我来回复

您尚未登录,请登录后再回复。点此登录或注册