Вирівнювання треку
Боб має завдання спланувати гоночну трасу певної довжини. Він вирішив, що чудовою ідеєю буде створити опуклий багатокутник, який точно відповідатиме потрібній довжині. Проте, йому повідомили, що гоночні автомобілі не можуть долати такі різкі повороти, як у його плані.
Боб повинен забезпечити мінімальний радіус для всіх кривих на своїй трасі. Йому дуже подобається форма його траси, тому він не хоче її сильно змінювати. Його план полягає в тому, щоб зменшити трасу навколо центру ваги багатокутника, що визначає його трасу. Потім він хоче намалювати нову трасу лінією, яка має постійну відстань до зменшеної траси. Обрана відстань повинна бути мінімальною, щоб відповідати заданому обмеженню мінімального радіуса. Він просить вас написати програму для обчислення коефіцієнта масштабування для заданої траси та мінімального радіуса, щоб отримана траса мала таку ж довжину, як і в його початковому плані.
Боб зробив кілька малюнків першого тестового випадку:
Вхідні дані
Вхідні дані починаються з кількості тестових випадків t (0 < t ≤ 100). Кожен тестовий випадок починається з рядка, що складається з двох цілих чисел: мінімально необхідного радіуса r і кількості точок n початкового багатокутника траси (0 ≤ r ≤ 1000, 3 ≤ n ≤ 10000). Потім слідує n рядків, де кожен рядок задає 2D-координати у вигляді двох цілих чисел x_i і y_i (-10000 ≤ x_i, y_i ≤ 10000). (0, 0) — це нижній лівий кут. Це координати початкової траси в напрямку проти годинникової стрілки. Ви можете безпечно припустити, що площа даного багатокутника не порожня.
Вихідні дані
Для кожного тестового випадку виведіть один рядок. Якщо можливо побудувати трасу відповідно до описаного вище, виведіть коефіцієнт масштабування, "Not possible" в іншому випадку. Коефіцієнт повинен мати відносну або абсолютну похибку меншу ніж 10^{-5}.