(Майже) Справедливе розрізання торта#11100

(Майже) Справедливе розрізання торта

1 секунда

128 мегабайтів

Складна

Ви, напевно, знаєте про справедливий спосіб розділити торт, коли одна людина розрізає його навпіл, а інша обирає, яку частину з'їсти. Це вважається справедливим, оскільки жоден з учасників не може сказати, що отримав меншу частину.

Але Аліса встановлює свої правила, і вони точно не повинні бути справедливими. Вона наказує своєму молодшому братові Бобу зробити $n$ розрізів, а не один. Тепер, для кожного розрізу, Аліса обирає одну зі сторін і з'їдає весь торт з цього боку. Після того, як вона закінчить, Боб з'їдає залишок.

Торт представлений у вигляді квадрата на декартовій площині (насправді це прямокутний паралелепіпед, але ми припускаємо, що всі розрізи перпендикулярні поверхні) з довжиною сторони $m$ . Боб щойно зробив $n$ розрізів, і тепер настав час Алісі зробити свій вибір. Визначте, скільки торта вона зможе з'їсти, якщо зробить правильний вибір.

Вхідні дані

Перша строка містить кількість тестів $z$ ( $1 \leq z \leq 500$ 1 \le z \le 500). Далі йдуть описи тестів.

Перша строка кожного набору вхідних даних містить два цілі числа $n$ ( $1 \leq n \leq 4000$ 1 \le n \le 4000) і $m$ ( $1 \leq m \leq 1000$ 1 \le m \le 1000) - кількість розрізів і довжина сторони торта. Торт являє собою квадрат, протилежні вершини якого розташовані в точках ( $0$ , $0$ ) і ( $m$ , $m$ ).

Потім слідують $n$ рядків, $i$ -й з яких містить три цілі числа $a_{i}$ a_i, $b_{i}$ b_i і $c_{i}$ c_i ( $- 1000 \leq a_{i}, b_{i} \leq 1000$ -1000 \le a_i, b_i \le 1000, $- 1 0^{6} \leq c_{i} \leq 1 0^{6}$ -10^6 \le c_i \le 10^6, $a_{i}^{2} + b_{i}^{2} > 0$ a_i^2 + b_i^2 > 0), які визначають лінійне рівняння $a_{i} x + b_{i} y + c_{i} = 0$ a_i x + b_i y + c_i = 0 $i$ -го розрізу.

Алісі надається набір з $n$ лінійних рівнянь. Для кожного рівняння їй потрібно замінити оператор = на ≤ або ≥, отримавши рівняння півплощини. Перетин торта з сумою $n$ таких півплощин - це те, що Аліса зможе з'їсти.

Кожен розріз ділить торт на дві частини ненульової площі кожна.

Загальна кількість розрізів у всіх тестах не перевищує $10000$ .

Вихідні дані

Для кожного тесту виведіть один рядок, що містить дійсне число $p$ ( $0 \leq p \leq 100$ 0 \le p \le 100) з $6$ десятковими цифрами, за яким слідує символ % - відсоток торта, який Аліса зможе з'їсти, якщо оптимально вибере всі сторони розрізів. Ваше рішення буде прийнято, якщо $p$ відрізняється від правильного відсотка не більше ніж на $0.000002$ %.

Приклади

Приклад 1