Поділіться тортами
Lunar Rose — це ніжна і добра дівчина, яка народилася в тихому містечку, і, як дивовижний збіг, це сталося на Свято середини осені того року. Тому на кожен свій день народження вона насолоджується двома тортами: одним на день народження і одним на свято.
Цього року Лунар захотіла поділитися тортами зі своїм хлопцем Джадді у цей чудовий день. Хіба це не романтично? Але сталася трагедія: Джадді знову все зіпсував.
Коли Лунар поставила два торти на стіл, вона попросила Джадді розрізати їх так, щоб кожен отримав половину місячного торта і половину торта на день народження. Але Джадді, будучи ледачим і імпульсивним, просто взяв ніж і розрізав їх разом, не дбаючи про рівність частин. Це розлютило Лунар, яка є перфекціоністкою, і вона дуже розсердилася на Джадді за його недбалість. Зрештою, Лунар вирішила залишити його. Дурний Джадді!
Джадді відчув глибокий жаль і засмучення. Лунар, будучи доброю дівчиною, не могла бачити його таким засмученим, тому вирішила дати йому ще один шанс. Однак вона поставила сувору умову: Джадді може зробити лише один розріз, щоб розділити обидва торти на рівні половини. О, ця сувора пані Роуз!
Обидва торти є опуклими багатокутниками; стіл і ніж досить великі й довгі, тому їх можна вважати нескінченними площинами і лінією. Допоможіть Джадді знайти стратегію, тобто лінію, яка задовольнить умову Лунар для розрізання тортів, щоб він міг повернути її прихильність.
Вхідні дані
Перша строка вхідних даних містить додатне ціле число T (T ≤ 100), що вказує кількість тестових випадків. Далі йдуть T випадків. Кожен тестовий випадок описує два торти (багатокутники): кожен багатокутник починається з цілого числа n, яке позначає кількість вершин, після чого йдуть n пар цілих чисел (x, y), що описують координати вершин проти годинникової стрілки. Ви можете припустити, що кожен багатокутник має не більше 20 вершин, і всі координати знаходяться в діапазоні від [-1000, 1000]. Крім того, два багатокутники можуть бути розділені лінією, не торкаючись жодної точки лінії.
Вихідні дані
Для кожного тестового випадку виведіть два дійсних числа k і b, починаючи з номера випадку, що означає, що Джадді повинен розрізати торти вздовж лінії y=k*x + b. Гарантується, що обидва k і b серед відповідей знаходяться в діапазоні від [-10000, 10000]. Дивіться приклад виходу для подальших деталей. Будь-яка відповідь з відносною або абсолютною похибкою 10^{-4} прийнятна.