블랙아웃
시간 제한3초메모리 제한1024 MB
b개의 전구 중 임의의 k개가 꺼져도 가로 w, 세로 l인 집 전체가 밝게 유지되는 최소 발전기 전류 c를 구합니다.
문제
Percy는 유령을 매우 무서워한다. 유령이 너무 무서워서, 동네에 정전이 났을 때 집 안 어디에 있든 유령과 함께 어둠 속에 갇히지 않도록 집에 발전기를 달고 싶어 한다. 그는 동네의 모든 집에 이런 발전기를 설치하고 싶어 한다.
각 집에는 여러 개의 조명이 있다. 각 조명에는 효율 값 p가 있다. 발전기가 전류 c를 생성하면, 조명은 반지름이 p×c인 원 영역을 밝힌다. 따라서 집 전체를 밝히는 데 필요한 최소 전류를 집마다 구할 수 있다.
Percy는 특히 더 걱정이 많다. 어떤 k개의 조명이 꺼지더라도 집 전체가 여전히 밝혀지는 최소 전류를 알고 싶어 한다. 집의 크기와 전구의 개수가 주어졌을 때, 임의의 k개의 전구가 꺼져도 집 전체를 밝힐 수 있는 최소 전류 c를 구하라.
입력
첫 줄에 집의 개수를 나타내는 양의 정수 n이 하나 주어진다. 각 집은 새 줄에 네 정수 b, k, w, l이 주어지며, 각각 전구의 개수, 꺼질 수 있는 전구의 개수, 집의 너비와 길이를 뜻한다(1 ≤ b ≤ 100, 0 ≤ k < b, 2 ≤ w ≤ 20000, 2 ≤ l ≤ 20000). 이어지는 b개의 줄에는 각각 세 정수 x, y, p가 주어진다. (x, y)는 전구의 위치(0 < x < w, 0 < y < l)이고, p는 그 효율(0 < p ≤ 20000)이다.
집은 (0, 0)부터 (w, l)까지 축에 평행한 직사각형이다.
출력
각 집에 대해, 어떤 k개의 전구가 꺼지더라도 집 전체가 밝혀져 있는 최소 전류를 출력한다. 값은 소수점 둘째 자리까지 출력한다. 판정 값과의 차이가 ±0.01 이내이면 정답으로 인정한다.