Авіаудар#1276

Авіаудар

1 секунда

64 мегабайти

Складна

Генерал Джі є командувачем військової бази. Щойно він отримав тривожну звістку від одного зі своїх шпигунів: ворог готує ракетний авіаудар. На базі розташовано дві магнітні вежі. Коли вони активовані й отримують достатню кількість енергії, кожна з цих веж створює потужний горизонтальний магнітний диск. Якщо будь-яка ракета проходить крізь цей диск, її буде відхилено від бази.

Хоча ці вежі здаються чудовим методом протиповітряної оборони, існує проблема: площа диска, який генерує вежа, пропорційна кількості отриманої нею енергії. На базі є достатньо електростанцій, щоб виробити певну кількість енергії, яку необхідно розподілити між цими двома вежами. Це означає, що сумарна площа двох дисків, які створюють вежі, не повинна перевищувати загальну енергію, вироблену електростанціями. На щастя, шпигун зміг дізнатися точні координати цілей для всіх ворожих ракет і передав їх генералові Джі. Генерал просить вас допомогти розподілити енергію між двома магнітними вежами так, щоб мінімізувати кількість ракет, які не будуть відхилені й, відповідно, уцілять по базі. Можна припустити таке:

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

Вхідні дані

Вхід складається з кількох тестових випадків. Кожен тестовий випадок задається в $N + 2$ N+2 рядках. Перший рядок містить одне ціле число ( $1 \leq N \leq 1000$ 1 \leq N \leq 1\,000), що вказує кількість ракет. Другий рядок містить $5$ дійсних чисел $X_{1}, Y_{1}, X_{2}, Y_{2}, T$ X_1, Y_1, X_2, Y_2, T: $(X_{1}, Y_{1})$ (X_1, Y_1) — координати першої вежі, $(X_{2}, Y_{2})$ (X_2, Y_2) — координати другої вежі, а $T$ — загальна енергія, вироблена електростанціями (сумарна площа двох магнітних дисків). Кожен з наступних $N$ рядків містить по дві дійсні координати точки приземлення ракети.

Абсолютне значення всіх заданих дійсних чисел не перевищує $100$ і вони можуть містити десяткову крапку з максимум $3$ знаками після неї. Будь-які два послідовних числа в одному рядку розділені одним чи кількома пробілами. Між тестовими випадками може бути будь-яка кількість порожніх рядків.

Останній рядок вхідного файлу складається з одного нуля.

Вихідні дані

Для кожного тестового випадку виведіть рядок у такому форматі:

k. M

де $k$ — номер тестового випадку (починаючи з $1$ ), а $M$ — мінімальна кількість ракет, які НЕ будуть відхилені за найкращого розподілу енергії між двома вежами. Використовуйте $π = 3.141$ \pi = 3.141.

Примітка: перед $M$ має бути пробіл.

Приклади

Приклад 1