最近二維點對
請利用最近二維點對演算法，解決最近二維點對問題。
以下給定 n 個二維平面點，找出其中距離最近的二個點的距離，例如：(5, 3), (9, 6), (5, 1) 最近二維點對距離為 2，則輸出至小數點後 3 位：2.000。
Input
第一行為 n 代表總共有 n 組二維點對問題。
第二行為 m 代表此二維點對共有 m 個點。
接下來的 m 行，每一行都是一個二維點的 x, y 座標，中間以空白隔開。
Output
輸出最近的點對距離，並且輸出至小數點後第 3 位，例如距離為 2 則輸出 2.000。
範例輸入：
3
2
5 3
9 6
3
5 3
9 6
5 1
4
5 3
9 6
5 1
4 4
範例輸出：
5.000
2.000
1.414
/*----- ----- ----- -----*/ //1-Closest pair of 2D points //Made by 105502555 Teemo Hsu(Synasaivaltos) //Date: 2018/04/24 /*----- ----- ----- -----*/ #include <iostream> #include <climits> #include <cmath> #include <iomanip> #include <vector> using namespace std; int main(void) { int n; cin >> n; vector<double> ans; ans.resize(n); fill(ans.begin(),ans.end(),INT_MAX); while(--n>=0) { int m; cin >> m; vector<double> x,y; x.resize(m); y.resize(m); while(--m>=0) { cin >> x.at(x.size()-m-1) >> y.at(y.size()-m-1); } for(int i=0;i<x.size();i++) { for(int j=i+1;j<y.size();j++) { if(ans.at(ans.size()-n-1)>pow((pow((x.at(i)-x.at(j)),2.)+pow((y.at(i)-y.at(j)),2.)),0.5)) ans.at(ans.size()-n-1)=pow((pow((x.at(i)-x.at(j)),2.)+pow((y.at(i)-y.at(j)),2.)),0.5); } } } for(int i=0;i<ans.size();cout<<fixed<<setprecision(3)<<ans.at(i)<<endl,i++); return 0; } |
