--->
144 задач
<---
Источники
Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером \(X\)×\(Y\) метров. Однако когда дизайнер стал выбирать место для фонтана, он столкнулся с серьезной проблемой: в холле института обнаружилось \(N\) круглых колонн, снести которые не представляется возможным.
Таким образом, у него появилась проблема: где следует поместить фонтан, чтобы он имел максимально возможный радиус и не имел ненулевого по площади пересечения с колоннами. Вам предстоит помочь ему в решении этой нелегкой задачи.
В первой строке входных данных содержатся вещественные числа \(X\) и \(Y\), 1 <= \(X\), \(Y\) <= \(10^4\) . Будем считать, что прямоугольник холла расположен на координатной сетке так, что его углы имеют координаты (0, 0), (\(X\), 0), (\(X\), \(Y\)) и (0, \(Y\)).
Во второй строке задается число \(N\) (0 <= \(N\) <= 10) - количество колонн. Следующие \(N\) строк содержат параметры колонн - \(i\)-я строка содержит три вещественных числа \(X_i\), \(Y_i\) и \(R_i\) - координаты центра и радиус \(i\)-й колонны (\(R_i\) <= \(X_i\) <= \(X\)-\(R_i\), \(R_i\) <= \(Y_i\) <= \(Y\)-\(R_i\), 0.1 <= \(R_i\) <= min(\(X\) / 2, \(Y\) / 2); для любых \(i\) ≠ \(j\) sqrt( (\(X_i\) - \(X_j\))2 + (\(Y_i\) - \(Y_j\))2 )>= \(R_i\) + \(R_j\)). Все вводимые числа разделены пробелами.
Выведите три вещественных числа: \(X_F\), \(Y_F\) и \(R_F\) - координаты центра и радиус фонтана. Фонтан должен быть полностью расположен внутри холла (допускается касание стен) и не иметь ненулевого пересечения ни с одной из колонн (допускается касание). Радиус фонтана должен быть максимален. Разделяйте числа пробелами и/или переводами строки. Если решений несколько, выведите любое из них.
10 10 0
5.000 5.000 5.000
1 1000 0
0.500 0.500 0.500
10 10 4 1 1 1 9 9 1 1 9 1 9 1 1
5.000 5.000 4.657
В декартовой системе координат на плоскости заданы координаты вершин треугольника и ещё одной точки. Определить, принадлежит ли эта точка треугольнику.
В четырёх строках находятся пары чисел - координаты точек. Числа в первых трёх строках - это координаты вершин треугольника, в четвёртой строке - координаты тестируемой точки. Координаты вершин - целые числа, для любой точки выполняются следующие условия: -10 000 <= \(x\), \(y\) <= 10 000.
Вывести слово "In", если точка находится внутри треугольника, или "Out" - если снаружи.
-2 -2 3 1 0 1 0 0
In
-2 -2 3 1 0 1 2 -2
Out
Два отрезка на плоскости заданы целочисленными координатами своих концов в декартовой системе координат. Требуется определить, существует ли у них общая точка.
В первой строке содержатся координаты первого конца первого отрезка, во второй - второго конца первого отрезка, в третьей и четвёртой - координаты концов второго отрезка. Kоординаты целые и по модулю не превосходят 10 000.
Выводится слово "Yes", если общая точка есть, или слово "No" - в противном случае.
-10000 -10000 10000 10000 -10000 10000 10000 -10000
Yes
10000 10000 -10000 -10000 -10000 10000 10000 -10000
Yes
0 0 7000 7000 5000 10000 10000 5000
No
Даны размеры прямоугольных открытки и конверта. Требуется определить, поместится ли открытка в конверт.
В первой строке находятся размеры открытки, во второй - размеры конверта. Pазмеры открытки и конверта - целые положительные числа, не превосходящие 100.
Если открытку можно вложить в конверт, вывести "Possible", если нет - вывести "Impossible".
10 15 14 10
Impossible
10 15 15 10
Possible
В прямоугольной декартовой системе координат прямая задана двумя принадлежащими ей точками (\(0\), \(W\)) и (100\(N\), \(E\)). Также заданы \(N^2\) квадратов со сторонами, параллельными осям координат. Квадрат \(S\)\(i\), \(j\) имеет координаты углов (100\(i\), 100\(j\)) и (100\(i\) - 100, 100\(j\) - 100), \(i\), \(j\) = 1, 2, ..., \(N\). Требуется найти количество квадратов, имеющих общую точку с прямой.
В первой строке находятся три целых числа, \(N\), \(W\) и \(E\), разделённых пробелами. 1 <= \(N\) <= 100, 0 <= \(W\), \(E\) <= 100\(N\), все числа целые.
Вывести одно число - количество квадратов.
1 10 40
1
2 110 120
2