D. 치즈 자르기

여러분 모두 International Cheese Processing Company를 들어 봤을 것이다. 치즈 덩어리를 정확히 같은 두께의 조각으로 자르는 이들의 기계는 고전이 되었다. 최근 이들은 구형 치즈(에담 등)를 조각으로 자를 수 있는 기계를 만들었다. 아니, 같은 두께가 아니라 모두 같은 무게로! 하지만 새로운 도전이 기다리고 있다. 스위스 치즈 자르기이다. 에멘탈 같은 스위스 치즈에는 구멍이 있고, 구멍의 크기는 제각각일 수 있다. 구멍이 있는 조각은 치즈가 적어서 구멍이 없는 조각보다 가볍다. 그래서 도전은 이것이다. 구멍이 있는 치즈를 같은 무게의 조각들로 자르기. 영리한 초음파 기술(태아와 유전을 스캔하는 데 쓰이는 것과 같은 기술)로 치즈 속 구멍의 위치를 마이크로미터 정밀도로 알아낼 수 있다. 이 문제에서는 구멍이 완전한 구라고 가정해도 된다. 자르지 않은 각 블록의 크기는 \(100 \times 100 \times 100\)이며 각 치수는 밀리미터 단위이다. 당신의 임무는 이를 같은 무게의 조각 \(s\)개로 자르는 것이다. 조각들은 너비 100 mm, 높이 100 mm가 되며, 각 조각의 두께를 결정하는 것이 당신의 일이다.

입력의 첫 줄에는 두 정수 \(n\)과 \(s\)가 주어지며, \(0 \le n \le 10\,000\)은 치즈에 있는 구멍의 수이고 \(1 \le s \le 100\)은 잘라 낼 조각의 수이다. 다음 \(n\)개의 줄에는 각각 구멍 하나를 설명하는 네 양의 정수 \(r\), \(x\), \(y\), \(z\)가 주어지며, \(r\)은 반지름이고 \(x\), \(y\), \(z\)는 중심의 좌표로 모두 마이크로미터 단위이다. 치즈 블록은 어떤 구멍에 속하는 점들을 제외하고 \(0 \le x\), y, \(z \le 100\,000\)인 점 (x, y, z)들을 차지한다. 절단은 \(z\) 축에 수직으로 이루어진다. 구멍들은 겹치지 않지만 닿을 수는 있고, 구멍들은 치즈 안에 완전히 들어 있지만 경계에 닿을 수는 있다고 가정해도 된다.

\(z = 0\)인 치즈 끝에서부터 시작하여 \(s\)개 조각의 두께를 밀리미터 단위로 출력한다. 출력의 절대 또는 상대 오차는 \(10^{−}^{6}\) 이하여야 한다.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2015