Рыцари Круглого Стола
В 573 году нашей эры король Артур правит всей Британией. Он справедливый правитель, любимый своим народом. Однако управление такой обширной страной — задача непростая и требует много усилий. К счастью, ему помогают самые благородные рыцари Круглого стола. Изначально этот совет состоял только из самых доблестных героев королевства, таких как сэр Гавейн, сэр Ланселот и сэр Галахад. Но недавно король Артур счел политически необходимым принять новых членов в этот священный круг. Основная причина этого в том, что в условиях длительного мира при его правлении гильдии начали требовать большего влияния на управление страной. "В конце концов, в мирное время хлеб важнее мечей, не так ли?" — сказал глава гильдии пекарей. Будучи исключительно справедливым и благородным правителем, Артур согласился.
Это привело к увеличению числа "рыцарей" Круглого стола. Артур обнаружил, что ему пришлось заказать гораздо больший стол у гильдии плотников (которые, в свою очередь, сразу же потребовали несколько мест за ним), и затем пришлось добавить новое крыло к замку Камелот, чтобы разместить его (можете догадаться, что запросили каменщики после этого).
Теперь еженедельные собрания Круглого стола стали довольно многолюдными. На самом деле, людей так много, что бывает трудно услышать друг друга, сидя на противоположных сторонах стола. Чтобы понять, насколько велика эта проблема, Артур хочет, чтобы вы вычислили, как далеко друг от друга сидят два самых удаленных члена Круглого стола. Ситуация усложняется тем, что за столом сидит конечное число людей, и они неравномерно распределены вокруг стола — некоторые сидят близко друг к другу (чтобы обсудить важные вопросы), в то время как другие предпочитают держаться подальше от своих соседей (например, представитель гильдии целителей и глава гильдии убийц).
Ваша задача — написать программу, которая вычисляет максимальное расстояние между любой парой стульев вокруг стола. Для этого вам предоставляется список углов (отсортированных против часовой стрелки), которые указывают расположение стульев вокруг стола. Радиус самого стола равен числу рыцарей, сидящих за ним.
Входные данные
Первая строка содержит количество сценариев. Каждый сценарий начинается со строки, содержащей число n стульев (3 ≤ n ≤ 10000). Далее следуют n строк, каждая из которых состоит из двух целых чисел p и q (0 ≤ p < q < 10^9), обозначающих угол 2p/q.
Выходные данные
Вывод для каждого сценария начинается со строки, содержащей "Сценарий #i:", где i — номер сценария, начиная с 1. Затем выведите максимальное встречающееся расстояние, округленное до двух знаков после запятой. Завершите вывод для сценария пустой строкой.