教室有 N＊N 個座位，但學生人數遠少於 N2。當學生就座後，老師想知道座位最近的兩位學生之間的距離。在這裡的距離，指的是歐氏距離。學生的座位座標分別是 (x, y)。
舉例來說，假設有三位學生入座，分別為 (1, 1)、(1, 3)、(2, 5)。這三點之中最近的兩點座標分別為 (1, 1) 和 (1, 3)，其距離為 2。請寫一個程式計算出位置最近的兩個學生之間的距離值。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 每組輸入兩行。第一行有兩個正整數 N (5 ≤ N ≤ 100) 及 M (3 ≤ M ≤ 20)，N 代表教室大小 (座位有 N＊N 個)，M 為學生個數。 第二行有 2＊M 個正整數 x1 y1 x2 y2 … xM yM，以空白分開，分別代表每個學生座位的 x 和 y 座標。 | 請輸出相距最近兩位學生的距離，輸出至小數點以下 4 位 (以四捨五入法計算)。 |
| 5 3 1 1 1 3 2 5 | 2.0000 |
| 20 6 7 7 8 9 12 17 5 11 13 4 3 2 | 2.2361 |
解題思路
收到 x 和 y 時，往前找其他的座標並且計算和其距離，計算座標時可以先不用進行根號的運算，使用 int 來存資料即可。計算完之後將 x 和 y 以 Pair 的方式存到一個 Vector 中。判斷到最小的距離後在使用 sqrt() 即可。
範例程式碼－ZeroJudge A583: 座位距離計算問題
#include <iostream>
#include <vector>
#include <math.h>
#include <stdio.h>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
vector<pair<int, int>>seats;
int min = -1;
for (int i = 0; i<M; i++) {
int x, y;
cin >> x >> y;
for (int j = 0; j<i; j++) {
const int distance = pow(x - seats[j].first, 2) + pow(y - seats[j].second, 2);
if (min == -1 || distance < min) min = distance;
}
pair<int, int>tmp;
tmp.first = x;
tmp.second = y;
seats.push_back(tmp);
}
const double ans = double(sqrt(min));
printf("%.4f\n", ans);
}
//ZeroJudge A583
//Dr. SeanXD