Миссия радиотехника состоит в создании сети из n антенн, разбросанных по обширной пустыне, которую можно представить в виде двумерной плоскости. Он установит радиус передачи каждой антенны равным одному и тому же неотрицательному вещественному числу r. Дальность действия антенны определяется как множество всех точек, расстояние до которых не превышает r. Если диапазоны двух антенн имеют общую точку, эти антенны могут напрямую взаимодействовать. Кроме того, если антенны A и B могут общаться, а также антенны B и C, то антенны A и C также могут общаться через антенну B. Радиотехник хочет соединить антенны в сеть, то есть сделать так, чтобы каждые две антенны могли общаться. Поскольку ему ограничил расходы на эту миссию, а большие радиусы требуют больше денег, он выберет наименьший возможный радиус ему решить эту проблему!
Вход Входная первая строка содержит целое число n (1 ≤ n ≤ 1000), количество антенн. Каждая из следующих n строк содержит целые числа xi и yi (0 = xi , yi = 109 ), координаты i-й антенны. Выход. Выведите минимальный радиус. Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает 10-6.
Оценка. В тестовых случаях стоит это означает, что 1 ≤ n ≤ 100.
R=A+B+C, где A=53₁₀, B=653₈, C=DA₁₆, R=R₂ Эту задачу можно решать разными выбор зависит от умения решающего выполнять сложение в той или иной системе счисления. Но в любом варианте, сначала нужно представить А, В, С в какой-то одной системе счисления.
Посмотрим, как это будет выглядеть, если пользоваться привычной нам десятичной системой. 653₈ = 6·8²+5·8¹+3·8⁰ = 6·64+5·8+3 = 427 DA₁₆ = 13·16¹+10·16⁰ = 218 R₁₀ = 53+427+218 = 698 Переводим полученное число в двоичную систему, получая R₂: 698/2=349, остаток 0 349/2=174, остаток 1 174/2=87, остаток 0 87/2=43, остаток 1 43/2 =21, остаток 1 21/2=10, остаток 1 10/2=5, остаток 0 5/2=2, остаток 1 2/2=1, остаток 0 1/2=0, остаток 1 Выписываем остатки в обратном порядке: 1010111010. Это и есть ответ.
А теперь допустим, что мы хорошо владеем восьмеричной системой счисления. 1) получим А₈ 53/8=6, остаток 5 6/8=0, остаток 6 Выписываем остатки в обратном порядке: А₈=65 2) получим С₈, для чего перейдем сначала в двоичную систему С₂=1101 1010 (просто заменяем каждую цифру четырьмя двоичными). А теперь разобьем справа налево полученное значение по три разряда и каждую полученную триаду заменим восьмеричной цифрой. 11 011 010₂ = 332₈ 3) Выполним сложение R₈=A₈+B₈+C₈ 65 740 +653 +332
740 1272 Складывать в восьмеричной системе просто, если знать одну маленькую хитрость. 8 отличается от 10 на 2, поэтому и результат сложения в восьмеричной системе на 2 больше, чем в десятичной, если число превышает 7. Смотрим: 5+3=8, но это в десятичной, а в восьмеричной это на 2 больше, т.е. 10. Поэтому мы пишем 0 и +1 идет в следующий разряд. 6+5=11 и еще +1 от переноса, итого 12. Но в восьмеричной на 2 больше, т.е. 14. 4 пишем. +1 перенос. 6 и +1 от переноса - 7. Вот и получили 740. 4) Мы нашли R₈, переходим к R₂. Заменяем каждую восьмеричную цифру тремя двоичными: 1272₈=1 010 111 010₂ Мы получили тот же ответ, что и в предыдущем расчета.
Так что - дело привычки. Второй вариант кажется "непосвященному" сложнее, но на самом деле в нем меньше арифметики и если нет под рукой калькулятора, то может оказаться и быстрее, и удобнее.
Одно из "быстрых по написанию" решений, не учитывающих фактор наличия упорядоченности массивов. Это разумно: за решение - не та цена, за которую есть смысл составлять и отлаживать эффективный алгоритм поиска по упорядоченным массивам.
// PascalABC.NET 3.1, сборка 1256 от 21.06.2016 begin var x:=ArrRandom(ReadInteger('p='),-20,20).Sorted; var y:=ArrRandom(ReadInteger('q='),-10,15).Sorted; var z:=ArrRandom(ReadInteger('r='),1,18).Sorted; x.Println; y.Println; z.Println; var r:=x.Intersect(y.Intersect(z)); if r.Count=0 then Writeln('Нет общих элементов') else begin Write ('Общие элементы: '); r.Println end end.
