15821번 - 낚이고 낚아라 서브태스크

낚시를 사랑하는 강태공 주띵이는 일반적인 낚시에 흥미를 잃기 시작했다. 새로운 방식의 낚시에 도전하기 위해 주띵이는 같은 동호회 사람들에게 '고인물 낚시'를 제안했다. 고인물 낚시는 넓은 강가나 바닷가가 아닌 작은 호수나 연못에서 낚시를 하는 방식이다. 낚시꾼은 육지의 한 위치에 자리를 고정하고 낚싯대의 긴 길이를 이용해 주변의 물가에 살고 있는 물고기를 잡아야 한다. 당연히 더 먼 거리에 낚시줄을 보낼 수 있는 좋은 낚싯대가 있을 수록 유리하다는 사실을 알 수 있다.

낚싯줄을 최대한 멀리 보낼 수 있는 거리를 낚시 거리라고 하며, 낚시 거리를 반지름으로 원을 그렸을 때 모든 영역이 원의 내부에 포함되는 낚시터를 유효 낚시터라고 한다.

그림1. N=6, K=5일 때의 예시

주띵이는 만족스러운 낚시를 위해 자신의 낚싯대를 업그레이드 하려고 한다. 하지만 예산이 한정적이므로, 자기 자리에서 최소 k개의 유효 낚시터를 확보할 수 있는 만큼만 업그레이드 하려고 한다. 위의 예시에서 낚시 거리가 11이상이 되면 다섯개의 유효 낚시터를 확보할 수 있다. 물론 더 낚시거리를 확장할 수 있지만, 이미 목표한 유효 낚시터를 모두 확보했으므로 그 중 최소인 11을 낚시 거리로 선택하는 것이 경제적이다.

현재 주띵이의 위치를 Z(0, 0)이라고 하자. 다각형 모양으로 생긴 각 낚시터들의 외곽선 정보가 입력으로 주어질 때, 주띵이가 K개 이상의 유효 낚시터를 확보하기 위한 최소의 낚시 거리를 계산해주자.

첫 줄에는 현재 존재하는 낚시터의 수를 나타내는 자연수 N과 주띵이가 요구하는 최소의 유효 낚시터의 수 K가 주어진다. N과 K는 모두 10만 이하의 자연수며 K는 항상 N이하의 값을 가진다. 이후 총 N개의 낚시터에 대한 정보가 차례로 주어진다. 각 낚시터의 정보는 두 줄로 구성되어 있다.

• 첫 줄에는 낚시터를 나타내는 도형의 꼭짓점 수를 나타내는 자연수 Pi가 입력으로 주어진다.
• 두 번째 줄에는 해당 낚시터의 꼭짓점들의 좌표가 공백으로 구분되어 주어지며, 각 좌표는 x y형식으로 주어진다. 모든 좌표는 첫 번째 점을 기준으로 시계방향 혹은 반시계방향으로 주어진다. 모든 좌표는 정수이다.
• 각 낚시터가 서로 겹치는 경우는 없으며, 각 낚시터는 항상 넓이가 0보다 큰 다각형이며 서로 교차하지 않는다.

최소 k개의 유효 낚시터를 확보할 수 있는 최소의 낚시 거리를 계산한 후, 이를 제곱한 값을 출력한다. 소수점 세 번째 자리에서 반올림하여 두 번째 자리까지 출력한다.

• 1 ≤ K ≤ N ≤ 100
• 3 ≤ P_i ≤ 10
• -100 ≤ x, y ≤ 100
• 모든 낚시터는 볼록 다각형이다. 볼록 다각형이란, 도형의 모든 내각이 항상 180도 이하가 되는 다각형이다.

• 1 ≤ K ≤ N ≤ 100,000
• 3 ≤ P_i ≤ 20
• -100,000 ≤ x, y ≤ 100,000

3번 예제는 문제 설명에 사용된 예시이다.