Точки (points.py)

Даны N точек на плоскости (для простоты можно считать, что у всех точек целочисленные координаты). Назовём расстояние от точки A до ближайшей к ней точки B "радиусом" точки A. "Соседями" точки A будем называть все точки, лежащие в пределах двойного радиуса от неё включительно (кроме самой точки A).

Для каждой точки из заданного набора определите её радиус и количество соседей.

Входные данные - набор строк, каждая строка состоит из координаты X и Y разделенных пробелом, переданных в stdin

Пример входных данных:

1 5

-3 1

7 2

-4 4

15 8

6 -7

Пример выходных данных:

R = 5.09901951359, neighbours = 3

R = 3.16227766017, neighbours = 2

R = 6.7082039325, neighbours = 5

R = 3.16227766017, neighbours = 2

R = 10.0, neighbours = 5

R = 9.05538513814, neighbours = 5

Алгоритм решения

Строим матризу расстояний между всеми точками на плоскости. Матрица симметричная, на главной диагонали нули. Каждая строка представляет собой набор расстояний от данной точки до любой другой.

Рассматриваем одну строку. Первое ненулевое значение (совпадающие точки считаем одной точкой) принимаем за радиус. Если следующее значение больше текущего радиуса, проверяем не является ли соседом. Если меньше, то возможны два варианта. Если текущий радиус меньше чем новое значение умноженное на два, проверяем найденных соседей с учётом нового радиуса. Если текущий радиус больше нового значения умноженного на два, проверять уже найденных соседей нет смысла, т.к. они заведомо дальше чем два радиуса.

Пройдя по каждой строке получаем список радиусов и количество соседей для каждой точки.

Дробь (division.py)

Даны два числа: a и b. Найдите значение числа a/b, записанного в k-ичной системе счисления. Если a/b — периодическая дробь, то период следует заключить в скобки.

Пример входных данных:

1 2 8

1 12 10

Пример выходных данных:

0.4

0.08(3)

Алгоритм решения

Если a > b, т.е. есть целая часть, вычисляем ее, запоминаем. Далее берем остаток от деления a / b. Запоминаем его значение. Домножаем его на основание системы счисления, до тех пор, пока полученное значение не будет больше b. С каждым домножением в дробную часть записываем 0. Далее целая часть от деления полученного числа на b идет в дробную часть нашего частного, остаток снова запоминаем и домножаем на основание с.с. Повторяем это до тех пор, пока не получим нулевой остаток, либо пока не получим такой остаток, который встречался на предыдущем шаге - это говорит о том, что дробь в дайнной системе счисления периодическая.