DIST
Cho \(𝑛\) điểm trên mặt phẳng, điểm thứ \(𝑖\) có tọa độ \((𝑥_𝑖,y_𝑖)\). Định nghĩa khoảng cách giữa điểm thứ \(𝑖\) với điểm thứ \(𝑗\) là \(𝐌𝐈𝐍 (|𝑥𝑖 − 𝑥𝑗|,|𝑦𝑖 − 𝑦𝑗|)\). Xét tất cả các cặp điểm, tạo ra dãy gồm \(𝑛×(𝑛−1)/2\) giá trị là khoảng cách tất cả các cặp điểm, sắp xếp các khoảng cách theo thứ tự tăng dần, hãy xác định giá trị thứ \(𝑘\).
Input:
Dòng đầu chứa hai số nguyên \(𝑛,𝑘;\)
Tiếp theo là \(𝑛\) dòng, dòng thứ \(𝑖\) chứa hai số nguyên không âm \(𝑥_𝑖,y_𝑖 (𝑥𝑖, 𝑦𝑖 ≤ 10^5). \)
Output:
- Gồm một dòng chứa một số là giá trị thứ \(𝑘\) tìm được.
Sample Input
4 2
0 0
1 0
0 1
1 1
Sample Output
0
Comments