c316: 最遠點對！前傳

2019-08-23

內容

在平面上有 N 個點，編號為 0~N-1，現在給你每個點的位置 (x, y)

請找出平面上哪兩個點間的距離最遠。

輸入

第一行有一個正整數 N，表示有平面上有 N 個點。

接下來 N 行每行有兩個整數 x y ，依序代表第 0 ~ N-1 個點的座標。

(1 <= N <= 1000)

(-1000 <= x, y <= 1000)

3
0 0
3 4
5 12

輸出

輸出兩個整數 i j ，中間用空白分隔，表示第 i 個點和第 j 個點離最遠 ( i < j )。

如果算出有最遠距離的點對有很多組，請輸出 i 最小的組，如果 i 一樣，則請輸出 j 最小的組。

舉例來說，假設平面上兩點間最遠的距離為 2，且第 5 個點和第 2 個點的距離為 2，第 3 個點和第 6 個點的距離亦為 2，則輸出「2 5」。

0 2

解題思路

簡單的迴圈 + 條件判斷。

一個小細節是由於 a 到 b 的距離 = b 到 a 的距離，所以計算時可以避開會重複計算到的區域。

完整程式碼

AC (5ms, 152KB)

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

typedef struct Point
{
    int X, Y;
}Point;

Point list[1010], ans;

int main()
{
    double best, tmp;
    int n;
    while (scanf(" %d", &n) == 1)
    {
        best = 0;
        for (int i = 0; i < n; i++)
        {
            scanf(" %d %d", &list[i].X, &list[i].Y);
            for (int j = 0; j < i; j++)
            {
                tmp = sqrt((list[i].X - list[j].X) * (list[i].X - list[j].X) + (list[i].Y - list[j].Y) * (list[i].Y - list[j].Y));
                if (best < tmp)
                {
                    best = tmp;
                    ans.X = j;
                    ans.Y = i;
                }
            }
        }
        printf("%d %d\n", ans.X, ans.Y);
    }
    return 0;
}