Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Стена#55170

Жил-был жадный Король. Он приказал своему главному Архитектору построить стену вокруг его замка. Король был таким жадным, что не послушал предложение Архитектора построить красивую кирпичную стену совершенной формы с изящными высокими башнями. Вместо этого он приказал построить стену вокруг всего замка, используя минимальное количество камня, но потребовал, чтобы стена не подходила к замку ближе некоторого расстояния. Если Король узнает, что Архитектор использовал больше ресурсов для постройки стены, чем было абсолютно необходимо для удовлетворения требований, Архитектор лишится головы. Более того, Архитектор должен представить проект стены, где указано точное количество ресурсов.

Ваша задача - помочь бедному Архитектору сохранить голову, написав программу, определяющую минимальную длину стены, которую можно построить вокруг замка, удовлетворив требования Короля.

Задача слегка упрощается тем, что замок Короля представляет собой многоугольник и расположен на плоской поверхности. Архитектор уже сопоставил замку прямоугольную декартову систему координат и точно определил координаты каждого угла замка в футах.

Входные данные
Первая строка содержит два целых числа N и L, разделённых пробелом: N - число углов в замке Короля, а L - минимальное число футов, на которое Король разрешил приблизить стену к замку.

Следующие N строк описывают координаты углов замка в порядке обхода по часовой стрелке. Каждая строка содержит два целых числа x_i и y_i, разделённых пробелом и представляющих собой координаты i-го угла в футах. Все углы имеют различные координаты, и стены замка не пересекаются иначе как в углах.

Ограничения: 3 <= N <= 1000, 1 <= L <= 1000, -10 000 <= x_i, y_i <= 10 000.

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

Многоугольники. Выпуклые оболочки Элементарная геометрия

✓ 1✗ 0—Войти и решать

Фонтан#55064

Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером X×Y метров. Однако когда дизайнер стал выбирать место для фонтана, он столкнулся с серьезной проблемой: в холле института обнаружилось N круглых колонн, снести которые не представляется возможным.

Таким образом, у него появилась проблема: где следует поместить фонтан, чтобы он имел максимально возможный радиус и не имел ненулевого по площади пересечения с колоннами. Вам предстоит помочь ему в решении этой нелегкой задачи.

Входные данные
В первой строке входных данных содержатся вещественные числа X и Y, 1 <= X, Y <= 10⁴ . Будем считать, что прямоугольник холла расположен на координатной сетке так, что его углы имеют координаты (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 + Rj). Все вводимые числа разделены пробелами.

Выходные данные
Выведите три вещественных числа: X_F, Y_F и R_F - координаты центра и радиус фонтана. Фонтан должен быть полностью расположен внутри холла (допускается касание стен) и не иметь ненулевого пересечения ни с одной из колонн (допускается касание). Радиус фонтана должен быть максимален. Разделяйте числа пробелами и/или переводами строки. Если решений несколько, выведите любое из них.

Бинарный поиск по ответу Квадродерево Элементарная геометрия

✓ 1✗ 2—Войти и решать

Дремучий лес - 2#54145

Будем говорить, что для наблюдателя лес является дремучим, если из своего текущего положения наблюдатель видит только деревья. Вам дана карта леса и координаты точки, в которой находится наблюдатель. Требуется определить, кажется ли лес дремучим данному наблюдателю.

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

Входные данные
Cначала вводится целое число N - количество деревьев (1≤N≤50000). Затем идут два числа, задающих координаты наблюдателя. Затем идет N троек чисел, задающих деревья (первые два числа тройки задают координаты центра, а третье - радиус). Все координаты задаются точно и выражаются вещественными числами, по модулю не превосходящими 100000 и записанными не более чем с 2 знаками после десятичной точки.

Выходные данные
В первой строке выведите сообщение YES, если лес является дремучим, и NO - иначе. Во втором случае во вторую строку необходимо вывести координаты точки, глядя в направлении которой наблюдатель не видит деревьев (то есть луч, вдоль которого смотрит наблюдатель, не проходит внутри деревьев и не касается ни одного из деревьев). Координаты нужно вывести не менее, чем с 3 знаками после десятичной точки. Координаты не должны превышать 300000. Расстояние между выданной точкой и наблюдателем должно быть не меньше 1.

Многоугольники. Выпуклые оболочки Элементарная геометрия

✓ 1✗ 2—Войти и решать

Прямоугольники#50551

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

Ваша задача – по данным о расположении рисунка и прямоугольной дырки определить, испортил ли Вася рисунок старшего брата, другими словами, есть ли на вырезанном Васей прямоугольнике хотя бы маленький фрагмент рисунка Пети.

Формат входных данных
Вам даны 8 целых чисел - $x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4$, где $(x_1, y_1)$ - координаты левого нижнего угла рисунка Пети, $(x_2, y_2)$ - координаты правого верхнего угла рисунка. Аналогично, $(x_3, y_3)$ - координаты левого нижнего угла вырезанного Васей прямоугольника, $(x_4, y_4)$ - координаты правого верхнего угла вырезанного прямоугольника. Гарантируется, что данные прямоугольники невырождены ($x_1 < x_2$, $y_1 < y_2$ и аналогичные неравенства для второго набора координат). Листок был не очень большим, поэтому каждое число по модулю не превосходит $10^4$.

Формат выходных данных
Выведите YES, если Вася испортил рисунок, и NO в противном случае.

Примечание

Вычислительная геометрия Элементарная геометрия

✓ 7✗ 22900средняяВойти и решать

Целые точки#38432

Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).

Формат входных данных
В первой строке содержится N (3 ≤N ≤1000) – число вершин многоугольника. В последующих N строках идут координаты (X_i, Y_i) вершин многоугольника в порядке обхода по часовой стрелке. X_i и Y_i - целые числа, по модулю не превосходящие 1000000.

Формат выходных данных
Вывести одно число – искомое число точек.

Примеры

№	Входные данные	Выходные данные
1	4 -1 -1 -1 1 1 1 1 -1	1
2	3 0 0 0 2 2 0	0

Многоугольники. Выпуклые оболочки НОД и алгоритм Евклида Элементарная геометрия

✓ 6✗ 231 100средняяВойти и решать

Площадь треугольника#27074

Входные данные

Шесть чисел – координаты трёх вершин треугольника.

Выходные данные

Одно число – величина площади треугольника.

Примеры

№	Входные данные	Выходные данные
1	1 1 2 4 3 2	2.50000

Вычислительная геометрия Элементарная геометрия

✓ 660✗ 1 268300лёгкаяВойти и решать

*Лапта#25963

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

Входные данные:

- в первой строке входных данных содержатся два числа: D — максимальное расстояние удара и N — количество соперников на поле (D и N натуральные числа, $D <= 1000$, $N <= 200$);
- в следующих N строках задается по три числа – начальные координаты x_i и y_i и максимальная скорость v_i соответствующего игрока (скорости и координаты — целые числа, $–1000 <= x_i <= 1000$, $0 <= y_i <= 1000$, $0 < v_i <= 1000$).
Никакие два игрока не находятся изначально в одной точке. Игрок, бьющий мяч, находится в точке с координатами (0,0). Мяч выбивается в точку с неотрицательной ординатой ($y >= 0$).

Выходные данные: выведите сначала время, которое потребуется игрокам, чтобы добежать до мяча, а затем координаты точки, в которую нужно выбить мяч. Если таких точек несколько, выведите координаты любой из них. Время и координаты нужно вывести с точностью $10^{–3}$.

Примеры

№	Входные данные	Выходные данные
1	10 2 1 1 1 -1 1 1	9.05539 0.00000 10.00000

Бинарный поиск по ответу Квадродерево Элементарная геометрия

✓ 7✗ 781 400средняяВойти и решать

Lots of Triangles#90362

Фермер Джон планирует планирует с выгодой продать часть своей земли. В его собственности находятся $n$ ($3 \leq N \leq 300$) деревьев, каждое описывается точкой на плоскости, никакие три из которых не коллинеарны. ФД хочет продать треугольный лот земли, определённый деревьями в своих вершинах. Имеется $L = \binom{N}{3}$ таких лотов, которые он может рассмотреть, перебирая все возможные тройки своих деревьев.

Треугольный лот имеет стоимость $v$ если он содержит ровно $v$ деревьев, внутри себя (деревья в вершинах не считаются, а на границах их и быть не может, поскольку по условиям все тройки деревьев не коллинеарны). Для каждого $v в интервале 0 \ldots N-3$, определите сколько из его $L$ потенциальных лотов имеют ценность $v$.

ФОРМАТ ВВОДА (файл triangles.in):

Первая строка ввода содержит $N$.

Каждая из последующих $N$ строк содержит $x$ и $y$ координаты одного дерева - целые числа в интервале $0 \ldots 1,000,000$.

ФОРМАТ ВЫВОДА (файл triangles.out):

Выведите $N-2$ строки, где строка $i$ содержит количество лотов с ценностью $i-1$.

Элементарная геометрия

—Войти и решать

Square Pasture#90357

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

Помогите ФД вычислить минимальную площадь, которую станет занимать его новое пастбище (покрывающее два исходных прямоугольника).

ФОРМАТ ВВОДА (файл square.in):

Первая строка входного файла описывает одно из оригинальных прямоугольных пастбищ четырьмя целыми числами, разделённых одиночными пробелами $x_1$ $y_1$ $x_2$ $y_2$ (все числа в диапазоне $0 \ldots 10$). Левый нижний угол пастбища – точка $(x_1, y_1)$, правый верхний угол – точка $(x_2, y_2)$, причём $x_2 > x_1$ и $y_2 > y_1$.

Вторая строка ввода аналогичным образом описывает второе прямоугольное пастбище. Оно не пересекается с первым и не касается его.

ФОРМАТ ВЫВОДА (файл square.out):

Вывод должен содержать одну строку содержащую минимальную площадь квадратного пастбища, которое покроет оба прямоугольника.

Задачи на моделирование Элементарная геометрия

—Войти и решать

Mountains#90142

**Обратите внимание: время на тест для этой задачи 5s, в 2.5 раза больше, чем обычно. Предельный размер памяти также увеличен в два раза по сравнению с умолчанием.

Имеется $N$ ($1 \leq N \leq 2000$) гор в ряд на ферме Джона Это может быть выражено как массив высот $h_1,h_2,\dots,h_N$. Для горы $i$, Вы можете увидеть другую гору $j$ если нет гор строго выше чем линия взгляда, соединяющая горы $j$ и $i$. Формально, для двух гор $i < j$, они могут видеть друг друга, если не существует такого $k$ $i < k < j$ и $(k, h_k)$ выше чем отрезок, соединяющий $(i, h_i)$ и $(j, h_j)$. Имеется $Q$ ($1 \leq Q \leq 2000$) изменений высот, когда высота одной горы возрастает. Определите общее количество неупорядоченных пар гор, которые могут видеть друг друга после каждого изменения.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Строка $1$ содержит $N$.

Строка $2$ содержит $N$ высот $h_1,h_2,\dots,h_N$ (для каждого $i$, $0 \leq h_i \leq 10^9$).

Строка $3$ содержит $Q$.

Строки $4$ - $3+Q$ содержат $x$, $y$ ($1 \leq x \leq N$, $1 \leq y$) где $x$ индекс горы, $y$ - величина на которую эта гора возрастает. Гарантируется, что новая высота горы не превысит $10^9$.

ФОРМАТ ВЫВОДА (на экран / stdout):

$Q$ строк, на каждой общее количество неупорядоченных пар гор, которые могут видеть друг друга после каждого обновления.

ПРМЕР ВВОДА:

Вычислительная геометрия

—Войти и решать

Mountain View#90071

Со своего пастбища Беси имеет прекрасный вид на горный горизонт. Имеется $N$ гор ($1 \leq N \leq 10^5$). Каждая гора это треугольник, основание которого лежит на оси $x$. Обе стороны горы наклонены под углом 45 градусов, поэтому пик горы - угол в 90 градусов. Гора $i$ поэтому задаётся координатами $(x_i, y_i)$ её пика. Никакие две горы не имеют одно и то же расположение пика.

Беси хочет посчитать все горы, но, поскольку все они примерно одного цвета, она не может увидеть гору, если её пик лежит на границе или внутри другой горы.

Определите количество различных пиков (и следовательно гор), которые Беси может увидеть.

ФОРМАТ ВВОДА (файл mountains.in):

Первая строка ввода содержит $N$. Каждая из оставшихся $N$ строк содержит $x_i$ ($0 \leq x_i \leq 10^9$) и $y_i$ ($1 \leq y_i \leq 10^9$) описывающих пики гор.

ФОРМАТ ВЫВОДА (файл mountains.out):

Выведите минимальное количество гор, которые Беси может различить.

Клеточная геометрия

—Войти и решать

Icy Perimeter#90070

Фермер Джон собирается выпускать и продавать мороженое. Он построил машину, которая производит шарики мороженого, но, к несчастью, немного неправильной формы.

Конфигурация мороженого, которое производится машиной, может быть описано решёткой $N \times N$ grid ($1 \leq N \leq 1000$):

##....
....#.
.#..#.
.#####
...###
....##

Каждый символ '.' представляет пустое место, а каждый символ '#' представляет $1 \times 1$ квадратную ячейку мороженого.

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

ФД хочет найти площадь и периметр сгустка, который имеет наибольшую площадь. Площадь сгустка равна количеству символов '#' в его картинке. Если несколько сгустков имеют одинаковую площадь, он хочет знать минимальный периметр из них. На рисунке выше, маленький сгусток имеет площадь 2 и периметр 6, а больший сгусток имеет площадь 13 и периметр 22.

Заметим, что сгусток может иметь "дыру" внутри (пустое пространство, окружённое мороженым). В таком случае граница "дыры" также учитывается в периметре сгустка. Сгусток может находиться внутри другого сгустка, в этом случае они рассматриваются как независимые сгустки. Например, ниже представлен сгусток площади 1 внутри сгустка площади 16:

#####
#...#
#.#.#
#...#
#####

ФОРМАТ ВВОДА (файл perimeter.in):

Первая строка ввода содержит $N$, а следующие $N$ строк описывают вывод машины. Присутствует, как минимум, один символ '#'.

ФОРМАТ ВЫВОДА (файл perimeter.out):

Выведите одну строку, содержащую два разделённых одиночным пробелом целых числа: площадь наибольшего сгустка и его периметр. Если есть несколько сгустков максимальной площади, вывести минимальный периметр.

Задачи на моделирование Клеточная геометрия Поиск компонент связности

—Войти и решать

Painting the Barn#90057

Фермер Джон красит одну сторону своего амбара маленькими прямоугольными областями, однако его отвлекают коровы, и в результате некоторые участки содержат больше слоёв краски, чем другие.

Мы можем описать эту сторону амбара как двумерную плоскость, на которой ФД красит $N$ прямоугольников, стороны каждого из которых параллельны осям координат, и каждый из которых описывается своим левым нижним и правым верхним углами.

ФД хочет применить несколько слоёв краски к амбару, чтобы не пришлось перекрашивать в ближайшем будущем. Однако он не хочет тратить время делая лишние слои краски. Он считает $K$ оптимальным числом слоёв краски. Помогите ФД определить, какая площадь будет покрыта ровно $K$ слоями краски после того, как он закрасит все свои прямоугольники.

ФОРМАТ ВВОДА (файл paintbarn.in):

Первая строка ввода содержит $N$ и $K$ ($1 \leq K \leq N \leq 10^5$). Каждая из оставшихся $N$ строк содержит четыре целых числа $x_1, y_1, x_2, y_2$ описывающих прямоугольный регион, который зарисовали левым нижним углом $(x_1, y_1)$ и правым верхним углом $(x_2, y_2)$. Все величины $x$ и $y$ находятся в интервале $0 \ldots 1000$, все прямоугольники имеют положительную площадь.

ФОРМАТ ВЫВОДА (файл paintbarn.out):

Выведите площадь амбара, которая покрыта ровно $K$ слоями краски.

Клеточная геометрия

—Войти и решать

Painting the Barn#90053

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

Мы можем описать эту сторону амбара как двумерную плоскость, на которой ФД рисует $N$ прямоугольников, стороны которых параллельны осям координат, Прямоугольники описываются координатами левого нижнего и правого верхнего углов.

ФД хочет покрасить амбар в несколько слоёв, так чтобы не пришлось вскорости снова красить. Однако, он не хочет тратить время на лишнюю покраску. Сначала он решил, что оптимально покрасить $K$ раз. Однако оглядев область Амбара, покрашенную ровно $K$ раз, он решил добавить два прямоугольника, Так, чтобы максимально увеличить площадь, покрашенную ровно $K$ раз, так чтобы эти прямоугольники не имели общей ненулевой площади пересечения. Заметим, что он может рисовать ноль новых прямоугольников или только один прямоугольник, если это может улучшить результат.

ФОРМАТ ВВОДА (файл paintbarn.in):

Первая строка ввода содержит $N$ и $K$ ($1 \leq K, N \leq 10^5$). Каждая из оставшихся $N$ строк содержит четыре целых числа $x_1, y_1, x_2, y_2$ описывающих прямоугольный регион левым нижним углом $(x_1, y_1)$ и правым верхним углом $(x_2, y_2)$. Все величины $x$ и $y$ в интервале $0 \ldots 200$, и все прямоугольники имеют положительную площадь.

Как и уже нарисованные прямоугольники, новые должны иметь положительную площадь, а координаты их углов $x$ и $y$ должны быть в интервале $0 \ldots 200$.

ФОРМАТ ВЫВОДА (файл paintbarn.out):

Выведите максимальную площадь амбара, которая может быть покрыта ровно $K$ слоями краски, если ФД закрасит ещё до двух дополнительных непересекающихся (по площади) прямоугольника.

Клеточная геометрия

—Войти и решать

Blocked Billboard II#90012

Корова Беси из окна видит два рекламных щита про вкусную пищу для коров. К несчастью, недавно один из этих щитов обновили, и теперь он рекламирует "Газонокосилки фермера Ларри". Беси не нравится эта реклама.

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

Беси решила удалить полностью щит с косилками из своего поля зрения, разработав рискованный план. Она планирует украсть огромный прямоугольный брезент из амбара и ночью покрыть оставшуюся видной часть щита с косилками так, чтобы никогда больше не видеть ни какой его части.

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

Формат ввода (файл billboard.in):

Первая строка ввода содержит четыре разделённых пробелом целых числа: $x_1$ $y_1$ $x_2$ $y_2$, где $(x_1, y_1)$ и $(x_2, y_2)$ - это координаты левого нижнего и правого верхнего углов щита с рекламой косилок. Следующая строка содержит четыре числа, которые аналогично описывают щит с рекламой коровьей еды. Этот щит может перекрывать весь щит с косилками, или его часть, или вообще его не перекрывать. Все координаты в интервале от -1000 до 1000.

ФОРМАТ ВЫВОДА (файл billboard.out):

Выведите минимальную площадь брезента, который нужен, чтобы покрыть видимую Беси часть щита с косилками полностью.

Элементарная геометрия

—Войти и решать

Blocked Billboard#89976

Во время дойки Беси любит смотреть в окно амбара на два огромных прямоугольных рекламных щита: "Farmer Alex's Amazingly Appetizing Alfalfa" и "Farmer Greg's Great Grain". Продукты на них выглядят вкуснее, чем трава на ферме.

Однажды глядя в окно, Беси увидела огромный прямоугольный грузовик, паркующийся поперёк дороги. На боку грузовика была реклама для "Farmer Smith's Superb Steaks", которую Беси не могла понять, и которая заслоняла её любимые рекламы.

Вам дано расположение двух рекламных щитов и грузовика, вычислите общую площадь двух рекламных щитов, которая видна. Возможно, что грузовик закрывает ни одного, один или оба щита.

Формат ввода (файл billboard.in):

Первая строка ввода содержит четыре числа, разделённых одиночными пробелами: $x_1$ $y_1$ $x_2$ $y_2$, где $(x_1, y_1)$ и $(x_2, y_2)$ - координаты левого нижнего и правого верхнего углов первого щита. Следующая строка ещё четыре числа - аналогично координаты левого нижнего и правого верхнего углов второго щита. Третья и последняя строка ввода аналогично содержит четыре целых числа указывающих левый нижний и правый верхний углы грузовика. Все координаты в интервале -1000 1000. Гарантируется, что первые 2 щита не имеют положительной площади пересечения.

Формат вывода (файл billboard.out):

Выведите общую площадь двух щитов, которая остаётся видимой.

Элементарная геометрия

—Войти и решать

The Lazy Cow#89939

Сегодня жаркий летний день, и корова Беси чувствует себя утомлённой. Она хочет так расположиться на поле, чтобы она находилась на коротком расстоянии от как можно большего количества вкусной травы.
Имеется N участков с травой (1 <= N <= 100,000) на поле Беси. i-ый из этих участков содержит g_i единиц травы (1 <= g_i <= 10,000) и расположен в различных точках (x_i, y_i) поля (0 <= x_i, y_i <=1,000,000). Беси хочет выбрать точку для своего начального расположения так, что бы максимальное количество травы было достижимо не более чем за K шагов от этого положения (1 <= K <= 2,000,000).
Шаг Беси – это перемещение на 1 единицу к северу, югу, востоку или западу от текущей позиции. Например, перемещение из точки (0,0) в точку (3,2) требует 5 шагов.
Пожалуйста, помогите Беси определить максимальное количество травы, Которое она сможет достичь, если выберет наилучшее начальное расположение.
PROBLEM NAME: lazy
Формат входных данных
* Строка 1: Целые числа N и K.
* Строки 2..1+N: Строка i+1 опсиывает i-ый участок травы используя 3 целых числа: g_i, x_i, y_i.
Формат выходных данных
* Строка 1: Максимальное количество травы, которое может достичь Беси за K шагов, если он выберет наилучшее начальное положение.
Примечание
Расположившись в точке (3,0) Беси обеспечит себе доступ к траве в позициях (0,0), (6,0), и (4,2) – все на расстоянии не превышающем K.

Клеточная геометрия

—Войти и решать

Cow Curling#89929

В коровий кёрлинг вовлечены две команды, каждая из которых двигает N тяжёлых камней (3 <= N <= 50,000) по льду. В конце игры имеется 2N камней на льду, каждый из которых расположен в различной точке плоскости.
Подсчёт очков в коровьем кёрлинге ведётся следующим образом: Камень считается «захваченным», если он содержится внутри треугольника, по углам которого находятся камни противника (камень, который находится на границе такого треугольника, также считается захваченным). Счёт команды есть количество камней команды противника, которые «захвачены».
Вычислите финальный счёт матча по коровьему кёрлингу, по заданному расположению всех камней.
PROBLEM NAME: curling
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды A (каждая координата лежит в диапазоне -40,000 .. +40,000).
* Строки 2+N..1+2N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды B (каждая координата лежит в диапазоне -40,000 .. +40,000).

Формат выходных данных
* Строка 1: Два разделённых пробелом целых числа, представляющих счета команд A и B
Примечание
Команда A захватила камень противника в точке (1,1). Команда B захватила камни противника в точках (0,2) и (2,2).

Многоугольники. Выпуклые оболочки

—Войти и решать

Line of Sight#89901

N (1 <= N <= 50,000) коров Фермера Джона распложены в различных точках двумерного пастбища. В середине пастбища расположен круглый элеватор. Коровы на противоположных сторонах элеватора не могут видеть друг друга, поскольку он заслоняет обзор.
Определите количество пар коров, которые могут видеть друг друга по прямой.
Элеватор расположен в точке (0,0) и имеет радиус R. Нет коров расположенных внутри или на границе этого круга. Также нет коров, Расположенных на касательных к этому кругу. R находится в диапазоне 1..1,000,000, и каждая корова находится в точке с целыми координатами в диапазоне -1,000,000..+1,000,000.
PROBLEM NAME: sight
Формат входных данных
* Строка 1: Два целых числа: N и R.
* Строки 2..1+N: Каждая строка содержит два целых числа, указывающих (x,y) координаты коровы
Формат выходных данных
* Строка 1: Количество пар коров, которые видят друг друга.
Примечание
Из 6 возможных пар не видят друг друга две «диагональные» пары коров: (-10,0) и (10,0), а также (0,-10) и (0,10)

Вычислительная геометрия

—Войти и решать

Farm Painting#89894

После нескольких суровых зим, Фермер Джон решил, что пришло время покрасить свою ферму. Ферма состоит из N (1 <= N <= 50,000) отгороженных пастбищ, каждое из которых может быть описано прямоугольником на 2D плоскости со сторонами, параллельными осям X и Y.
Пастбища могут содержаться один внутри другого, но их изгороди не могут пересекаться. Поэтому, если два пастбища покрывают одну и ту же область на 2D плоскости, то одно должно содержаться внутри другого.
ФД понимает, что пастбище, содержащееся внутри другого, не видимо снаружи. Поэтому он хочет красить изгороди только тех пастбищ, которые не содержатся внутри других пастбищ.
Определите общее количество пастбищ, изгороди которых он должен покрасить.
PROBLEM NAME: painting
Формат входных данных
* Строка 1: Количество изгородей, N.
* Строки 2..1+N: Каждая строка описывает изгородь 4-мя целыми числами x1, y1, x2, y2 (разделенных одиночными пробелами), где (x1,y1) - левый нижний угол изгороди, (x2,y2) - правый верхний уго изгороди. Все координаты в диапазоне 0..1,000,000.
Формат выходных данных
* Строка 1: Количество пастбищ, которые не содержатся внутри других пастбищ.
Примечание
Пастбище 3 содержится внутри пастбища 1, поэтому ответ 2.

Вычислительная геометрия

—Войти и решать