Козла пустили в квадратный огород и привязали к колышку. Колышек воткнули точно в центре огорода. Козёл голоден, как волк, прожорлив, как бык, и ест всё, до чего дотянется, не перелезая через забор и не разрывая веревку. Какая площадь огорода будет объедена?

Петр Васильевич в ярости! Ведь сосед Василий Петрович выгуливал козла в его огороде! Как не предусмотрителен был Василий Петрович ведь у Петра Васильевича целых 2 козла и оба они в ответ будут поедать и вытаптывать соседский огород. Огород Василия Петровича большой и неогороженный, в некоторых его местах растут деревья. Козлам потребуется много времени, чтобы выполнить свою миссию. Поэтому Петр Васильевич решил привязать каждого козла к какому-нибудь дереву, и пусть себе гуляют. Но привязать каждого надо так, чтобы он не доставал до всех деревьев кроме того, к которому он привязан, иначе он запутается в веревке. Кроме того, надо чтобы они не доставали друг до друга, иначе они будут вытаптывать одну и ту же территорию. Чтобы нанести максимальный вред своему соседу, Петр Васильевич хочет, чтобы суммарная площадь, доступная козлам была максимальна. Но нельзя привязывать козла на расстоянии меньше 1 метра от дерева и дальше, чем на 50 метров.

На планете Плюк открылся новый космический кегельбан. Поле для кегельбана представляет собой бесконечную плоскость, на которой расставлены кегли.

Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом r метров. Все кегли одинаковые. Кегли расставлены по следующим правилам. Кегли образуют n рядов, в первом ряду стоит одна кегля, во втором — две, и так далее. В последнем n-м ряду стоит n кеглей. Введем на плоскости систему координат таким образом, чтобы единица измерения была равна одному километру. Центр единственной кегли в первом ряду находится в точке (0, 0). Центры кеглей во втором ряду находятся в точках (–1, 1) и (1, 1). Таким образом, центры кеглей в i-м ряду находятся в точках с координатами (–(i – 1), i –  1), (–( i – 3), i – 1), …, (i – 1, i – 1).

Игра происходит следующим образом. Используется шар с радиусом q метров. Игрок выбирает начальное положение центра шара (x_c,  y_c) и вектор направления движения шара (v_x, v_y). После этого шар помещается в начальную точку и двигается, не останавливаясь, в направлении вектора (v_x, v_y). Считается, что шар сбил кеглю, если в процессе движения шара имеет место ситуация, когда у шара и кегли есть общая точка. Сбитые кегли не меняют направления движения шара и не сбивают соседние кегли при падении.

На рисунке приведен пример расположения кеглей для r = 500, n = 4 и шара для q = 1000, x_c = –2, y_c = –2, v_x = 1, v_y = 1.

Требуется написать программу, которая по заданным радиусу кегли r, количеству рядов кеглей n, радиусу шара q, его начальному положению ( x_c, y_c) и вектору направления движения (v_x,  v_y) определяет количество кеглей, сбитых шаром.

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