2018 KAIST RUN Spring Contest |
---|
Finished |
In the year 5013, jh05013 conquered the Eurasian Continent and found "jh land". "jh land" encompasses the whole continent, and jh05013 aims to divide the country into “districts” to govern them efficiently, since it is extremely large and populated. There are N houses in "jh land", and each house is located at (xi, yi) of a 2D Cartesian coordinate system. jh05013 keeps the following conditions when dividing them into districts:
There are diverse races, religions, and nations in the Eurasian Continent. To avoid disputes, we must reduce the "splittedness" of districts. The splittedness of a district is defined as the distance between the farthest pair of houses contained in the district. The distance is measured in Euclidean metric. Help jh05013 minimize the maximum splittedness among districts.
In the first line, two space-separated integers N, K are given. N denotes the number of houses and K denotes the number of districts. (1 ≤ K ≤ N ≤ 250, 000)
In the next N lines, two space-separated integers xi, yi are given. They denote that a house is located at (xi, yi). ( 0 ≤ xi, yi ≤ 109) Every given location is distinct.
When the minimum of maximum splittedness among districts is M, print M2.
4 2
101 100
2 5
100 101
4 3
8
4 4
3 1
4 1
5 1
9 2
0
Name |
---|