Теперь вас назначили управляющим одной телекоммуникационной компании. Вы отвечаете за обеспечение маленького городка контентом. Каждый дом задается его координатами на плоскости. Известно, что никакие три дома не лежат на одной прямой, а никакие четыре на одной окружности. Вы решили поставить одну антенну так, чтобы сигнал от нее был доступен домам в определенным радиусе, т.е. область, в которой доступен контент является кругом. Вы еще не очень разобрались в политике вашей компании, поэтому решили сделать не слишком сложный выбор данной области: вы просто выбираете 3 случайных дома и строите круг так, чтобы эти три дома были на его границе (вы ходили на геометрию в 7 классе и вам известно, что так всегда можно сделать). Теперь вам интересно, сколько в среднем домов будут иметь доступ к контенту. Выведите ответ с точностью до 4 знаков после запятой.

Будем считать, что карта Адриатического моря представляет собой сетку, состоящую из единичных квадратиков, организованных в \(2500\) рядов и \(2500\) столбцов. Ряды пронумерованы от \(1\) до \(2500\) с севера на юг, столбцы пронумерованы от \(1\) до \(2500\) с запада на восток. В море есть N островов, пронумерованных от 1 до N и каждый остров находится внутри некоторого единичного квадрата сетки. Позиция острова K задана его координатами — рядом \(R_k\) и столбцом \(C_k\). Никакие два острова не находятся в одном квадрате.

Из за ветра и морских течений, за один шаг переплыть с одного острова на другой можно только, если они расположены в северо-западном или юго-восточном направлении друг относительно друга.

Точнее, можно переплыть с острова \(A\) на остров \(B\) за один шах, если или \(R_A \lt R_B\) и \(C_A \lt C_B\), или \(R_A \gt R_B\) и \(C_A \gt C_B\). При этом расстояние между островами или наличие островов по дороге не влияет на возможность доплыть с одного острова на другой. Если нельзя доплыть с одного острова на другой напрямую, иногда можно доплыть с использованием промежуточных островов более чем за один шаг. Определим как расстояние между островами величину, равную числу шагов, необходимых, чтобы переплыть с одного острова на другой.

Рассмотрим остров K. Для каждого острова определим, какое минимальное число шагов можно переплыть с него на K. Просуммируем эти числа и получим некоторую величину, характеризующую удаленность K от остальных островов. Требуется найти это число для всех островов. Гарантируется, что в тестах острова расположены так, что с каждого острова можно попасть на каждый.

Байтазар, король Байтотии организовал масштабную реформу имён своих подданных. Имена жителей Байтотии исторически часто содержат повторяющиеся фразы и Байтазар хочет с одной стороны упростить имена, а с другой, сохранить традиции повторения, а именно Байтазар хочет заменить каждое из имён в Байтотии на имя такой же длины, чтобы при этом множества периодов для старого и нового имён совпали, но имя при этом состояло только из символов «0» и «1». Из всех кандидатов в новое имя Байтазар хочет выбрать лексикографически минимальное.

Натуральное число \(k\) (\(1 \le k \lt n\)) называется периодом строки \(s\) длины \(n\) тогда и только тогда, когда для любого натурального \(i\), такого что \(1 \le i \le n - k\), верно что \(s_i = s_{i + k}\).

Множество периодов для данной строки \(s\) – множество таких чисел \(i\), что \(i\) является периодом \(s\). Обозначим его за Per(\(s\)). К примеру, Per(«ABIABUABIAB») = {6, 9}, Per(«0000») = {1, 2, 3}.

Помогите Байтазару перевести имена его подданных, и, возможно, он разрешит вам сохранить ваше собственное имя!