Поділіться тортами#3092
Lunar Rose — чиста й добра дівчина, яка народилася в мирному містечку і, до того ж, саме в рік Свята середини осені. Тому щороку на свій день народження вона ласує двома тортами: одним на своє свято, іншим — на фестиваль.
Цього року Lunar хоче поділитися тортами з Jaddy, своїм хлопцем, у цей чудовий день — хіба це не романтично? На жаль, Jaddy знову все зіпсував:
Коли Lunar поставила два торти на стіл, вона попросила Jaddy розрізати їх так, щоб кожен отримав по половині святкового і половині іменинного торта. Проте Jaddy, будучи лінивим і недбалим, просто взяв ніж і розрізав їх разом, не замислюючись. В результаті обидва торти були розрізані навпіл, але шматки виявилися нерівними. Гірше того, Lunar, яка була перфекціоністкою, дуже розсердилася на Jaddy за його недбалість і вирішила піти від нього. Бідний Jaddy!
Jaddy відчув глибокий жаль і сум. Lunar, маючи добре серце, не захотіла бачити його таким засмученим і вирішила дати йому ще один шанс. Однак вона поставила сувору вимогу: Jaddy може зробити лише один розріз, щоб поділити обидва торти порівну. Сувора міс Роуз!
Обидва торти є опуклими багатокутниками; вважаємо, що стіл і ніж настільки великі й довгі, що їх можна розглядати як нескінченну площину та пряму. Ваше завдання — допомогти Jaddy знайти стратегію — лінію, яка задовольнить вимогу Lunar, щоб він міг повернути її прихильність.
У першому рядку міститься одне ціле число (T \leq 100) — кількість тестових випадків. Далі йдуть тестів. Кожний тестовий випадок описує два торти (багатокутники): кожен багатокутник починається з числа — кількості вершин, за яким слідують пар цілих чисел , які описують координати вершин у порядку проти годинникової стрілки. Можна вважати, що в кожному багатокутнику не більше вершин, а всі координати лежать у межах . Крім того, обидва багатокутники можна розділити прямою, яка не проходить через жодну з їхніх точок.
Для кожного тестового випадку виведіть два дійсних числа і , починаючи з номера випадку, які означають, що Jaddy повинен розрізати торти по прямій y = kx + b. Гарантується, що в усіх відповідях і лежать у межах . Дивіться приклад виводу для деталей. Будь-яка відповідь із відносною або абсолютною похибкою не більше 10^{-4} приймається.
Приклад 1