The classroom has N*N seats, but the number of students is much less than N2. After the students have taken their seats, the teacher wants to know the distance between the two closest students. Here, distance refers to the Euclidean distance. The coordinates of the students' seats are (x, y).
For example, suppose there are three students seated at coordinates (1, 1), (1, 3), and (2, 5). The two closest points among these three are (1, 1) and (1, 3), with a distance of 2. Please write a program to calculate the distance between the two students who are closest in position.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| Each input consists of two lines. The first line contains two positive integers, N (5 ≤ N ≤ 100) and M (3 ≤ M ≤ 20), where N represents the size of the classroom (there are NN seats), and M represents the number of students.
The second line contains 2M positive integers x1 y1 x2 y2 ... xM yM separated by a space, representing the x and y coordinates of each student's seat. | Please output the distance between the two closest students, rounded to 4 decimal places (rounded using the round half-to-even method). |
| 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 |
Thought Process
Received the coordinates x and y, look ahead for other coordinates, and calculate the distance from them. When calculating the coordinates, you can store the data using int without performing square root operations. After calculating, store x and y as a Pair in a Vector. Once you find the minimum distance, use sqrt() to calculate it.
Sample Code－ZeroJudge A583: Seats Distances
#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