Balonu Partlatma
Açıq üstü olan kvadrat dibli bir qutu döşəməyə yerləşdirilib. Siz qutunun dibinə şaquli şəkildə əkilmiş bir sıra iynələr görürsünüz.
Sizin məqsədiniz qutunun dibinə toxunan, yan divarlarla və ya iynələrlə toqquşmayan ən böyük sferik şarı yerləşdirməkdir.
Java Xüsusi: Təqdim olunan Java proqramları "java.awt.geom.Area" istifadə edə bilməz. Siz onu öz səhvlərinizi düzəltmək üçün istifadə edə bilərsiniz.
Şəkil 1 iynələr olan qutunun və müvafiq ən böyük sferik şarın nümunəsini göstərir. Bu, aşağıdakı nümunə girişinin ilk məlumat dəstinə uyğundur.
Giriş verilənləri
Giriş bir neçə məlumat dəstindən ibarətdir. Hər bir məlumat dəsti aşağıdakı formatda verilir:
n w
x_1 y_1 h_1
...
x_n y_n h_n
Məlumat dəstinin ilk sətri boşluqla ayrılmış iki müsbət tam ədədi, n və w ehtiva edir. Burada, n iynələrin sayını, w isə yan divarların hündürlüyünü göstərir.
Qutunun dibi 100×100 ölçülü kvadratdır. Alt üzün küncləri (0, 0, 0), (0, 100, 0), (100, 100, 0) və (100, 0, 0) mövqelərində yerləşir.
Birinci sətrdən sonra gələn hər bir n sətri üç tam ədəd, x_i, y_i və h_i ehtiva edir. Burada, (x_i, y_i, 0) və h_i i-ci iynənin əsas mövqeyini və hündürlüyünü göstərir. Heç bir iki iynə eyni mövqedə yerləşmir.
Siz qəbul edə bilərsiniz ki, 1 ≤ n ≤ 10, 10 ≤ w ≤ 200, 0 < x_i < 100, 0 < y_i < 100 və 1 ≤ h_i ≤ 200. Siz iynələrin və divarların qalınlığını nəzərə almaya bilərsiniz.
Girişin sonu iki sıfırdan ibarət sətr ilə göstərilir. Məlumat dəstlərinin sayı 1000-i keçmir.
Şəkil 1. Üst hissə nümunə düzülüşünü və alt hissə yerləşdirilə bilən ən böyük sferik şarı göstərir.
Çıxış verilənləri
Hər bir məlumat dəsti üçün qutunun dibinə toxunan, yan divarlarla və ya iynələrlə toqquşmayan şarın maksimum radiusunu ehtiva edən bir sətir çıxarın. Çıxış 0.0001-dən böyük olmayan bir səhv ehtiva etməlidir.