Вычислительная геометрия — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(задание 3)
Строка 75: Строка 75:
 
0 2<br/>
 
0 2<br/>
 
3 0<br/>
 
3 0<br/>
 +
|}
 +
 +
 +
=== Задание 4. 2d-tree ===
 +
 +
Дано множество точек. Запрос — прямоугольник со сторонами параллельными осям координат, ответ — количество точек которые попадают в прямоугольник. Для реализации использовать 2d-tree, прямоугольник считать замкнутым (считается, что точки на границе входят в него). <br/>
 +
Формат инпута: на первой строке n - число точек, далее n строк с точками в обычном формате. На следующей строке m - число запросов, далее m строк с запросами в формате x1 x2 y1 y2 — прямоугольник <math>[x_1, x_2]\times[y_1, y_2]</math>. <br/>
 +
Вывести m строк с ответами на каждый запрос.
 +
 +
Пример (неофициальный):
 +
{| border=1 cellspacing=0 cellpadding=5px width=200px
 +
|-
 +
! input
 +
! output
 +
|- valign="top" padding=5
 +
|
 +
4 <br/>
 +
(1, 1) <br/>
 +
(2, 2) <br/>
 +
(3, 3) <br/>
 +
(3, 1) <br/>
 +
3 <br/>
 +
1 4 2 4 <br/>
 +
0 5 0 5 <br/>
 +
1 2 3 4 <br/>
 +
|
 +
2 <br/>
 +
4 <br/>
 +
0 <br/>
 
|}
 
|}

Версия 12:42, 29 октября 2014

Лектор - Андрей Давыдов andrey.a.davydov@gmail.com

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

Задание 1. Проверка принадлежности точки полигону

Дедлайн: 17.09

На вход N вершин полигона в формате (x, y) [abs(x), abs(y) <= 10^5] и M точек запроса. На выходе — M строк yes/no. Полигон всегда корректный, закрученный против часовой стрелки. Полигон считать замкнутым, т.е. для точек на границе ожидаемый ответ — yes.

input output

3
(0, 0)
(3, 0)
(0, 2)
3
(0, 1)
(1, 1)
(2, 1)

yes
yes
no


Задание 2. Триангуляция монотонного полигона

Дедлайн: 1.10

На вход полигон в том же формате и с теми же ограничениями на координаты, что в первом задании. Гарантируется, что полигон монотонен относительно OX, закручен против часовой стрелки, и первая вершина в инпуте — самая левая. Требуется разбить его на треугольники. На выходе N-2 тройки индексов (номеров вершин полигона) — треугольники на соответствующих вершинах. Формат троек такой же как точек в инпуте, то есть (i, j, k). Треугольники должны быть закручены против часовой стрелки, среди возможных троек представляющих один и тот же треугольник нужно выбирать наименьшую лексикографически. Сами тройки могут идти в любом порядке. Вершины полигона нумеруются с 0.

Пример (неофициальный):

input output

4
(0, 0)
(1, 0)
(1, 1)
(0, 1)

(0, 1, 2)
(0, 2, 3)


Задание 3. Поиск касательных к выпуклому полигону

На входе выпуклый полигон закрученный против часовой стрелки, заданный как обычно: т.е. число вершин n на первой строке и затем n строк вида (x, y), где x, y -- целые и |x|, |y| <= 10^5. Далее во входном потоке идет строка c числом запросов m и m строк с запросами, т.е. точками вне полигона, из которых мы хотим построить касательные. На выходе ожидается m строк с парами индексов вершин, в которых происходит касание (в литературе иногда эти вершины называются основаниями опорных прямых). Если касательная проходит через сторону полигона, в ответ выдавать индекс той вершины, которая ближе к точке запроса. Один запрос должен обрабатываться за O(log n).

input output

4
(0, 0)
(1, 0)
(1, 1)
(0, 1)
2
(2, -1)
(-2, 0)

0 2
3 0


Задание 4. 2d-tree

Дано множество точек. Запрос — прямоугольник со сторонами параллельными осям координат, ответ — количество точек которые попадают в прямоугольник. Для реализации использовать 2d-tree, прямоугольник считать замкнутым (считается, что точки на границе входят в него).
Формат инпута: на первой строке n - число точек, далее n строк с точками в обычном формате. На следующей строке m - число запросов, далее m строк с запросами в формате x1 x2 y1 y2 — прямоугольник .
Вывести m строк с ответами на каждый запрос.

Пример (неофициальный):

input output

4
(1, 1)
(2, 2)
(3, 3)
(3, 1)
3
1 4 2 4
0 5 0 5
1 2 3 4

2
4
0

Источник — «http://mit.spbau.ru/sewiki/index.php?title=Вычислительная_геометрия&oldid=4538»