Геометрические задачи

• «Растровые» и «аналитические» задачи. Недопустимость растровых алгоритмов для решения аналитических задач

• Элементы аналитических задач (на примере MCCME)

• Точность при решении аналитических задач

• Растровая прямая и antialiasing

Домашнее задание

1. Освежить в памяти уравнение прямой и окружности, пересечения прямых, окружности и касательной к ней и т. п.

2. Дано: координаты точки A на плоскости, список координат вершин многоугольника B₁ B₂ … B_i, … в порядке обхода. Требуется выяснить, принадлежит ли точка A выпуклому многоугольнику B₁B₂… (выпуклость гарантируется)

3. Те же условия, но многоугольник может быть невыпуклый.

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

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

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

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

Условные обозначения

• — тема по Linux

• ­— необязательная тема

• — теоретическое задание

• — тема для самостоятельного изучения

CategoryClass CategoryVmsh