(Əsasən) Ədalətli tort kəsimi
Siz yəqin ki, tortu ədalətli şəkildə kəsmə üsulunu bilirsiniz: bir nəfər tortu iki yerə bölür, digəri isə hansı hissəni yemək istədiyini seçir. Bu üsul ədalətli sayılır, çünki heç kim daha kiçik bir hissə aldığını iddia edə bilmir.
Amma Alisa qaydaları özü müəyyən edir və bu qaydalar mütləq ədalətli olmaq məcburiyyətində deyil. O, kiçik qardaşı Bobdan bir deyil, n kəsik etməyi tələb edir. Hər kəsikdən sonra Alisa tərəflərdən birini seçir və həmin tərəfdəki tortu yeyir. Kəsmə prosesi bitdikdən sonra Bob qalan tortu yeyir.
Tort Dekart müstəvisində kvadrat şəklində təsvir edilir və tərəfin uzunluğu m-dir. Bob artıq n kəsik edib və indi Alisanın seçim etmə vaxtıdır. Əgər Alisa düzgün seçim etsə, nə qədər tort yeyə biləcəyini müəyyən edin.
Giriş məlumatları
Birinci sətir testlərin sayı z (1 ≤ z ≤ 500) ehtiva edir. Sonra testlərin təsvirləri gəlir.
Hər bir giriş dəstinin birinci sətiri iki tam ədəd n (1 ≤ n ≤ 4000) və m (1 ≤ m ≤ 1000) - kəsiklərin sayı və tortun tərəfinin uzunluğunu ehtiva edir. Tort kvadrat şəklindədir və əks zirvələri (0, 0) və (m, m) nöqtələrində yerləşir.
Sonra n sətir gəlir, i-ci sətir üç tam ədəd a[i], b[i] və c[i] (-1000 ≤ a[i], b[i] ≤ 1000, -10^6 ≤ c[i] ≤ 10^6, a[i]^2 + b[i]^2 > 0) ehtiva edir, hansı ki a[i] x + b[i] y + c[i] = 0 i-ci kəsiyi təyin edən xətti tənlikdir.
Alisaya n xətti tənliklər dəsti verilir. Hər bir tənlik üçün o, operatoru = ilə ≤ və ya ≥ ilə əvəz etməlidir, yarım müstəvi tənliyi əldə etmək üçün. Tortun n belə yarım müstəvilərin cəmi ilə kəsişməsi Alisaya yeməyə icazə verilən hissədir.
Hər bir kəsik tortu hər biri sıfırdan fərqli sahəyə malik iki hissəyə bölür.
Bütün testlərdə ümumi kəsiklərin sayı 10 000-i keçmir.
Çıxış məlumatları
Hər bir test üçün bir sətir çıxarın, burada p (0 ≤ p ≤ 100) real ədədi və ardınca % simvolu - Alisanın bütün kəsiklərin tərəflərini optimal seçərsə yeyə biləcəyi tortun faizi. Həlliniz qəbul ediləcək, əgər p düzgün faizdən 0.000002%-dən çox fərqlənmirsə.