DIST


Submit solution

Points: 100
Time limit: 2.0s
Memory limit: 299M

Problem type

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

There are no comments at the moment.