Вычислительная геометрия — различия между версиями
(Добавил второе задание) |
м |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 51: | Строка 51: | ||
(0, 2, 3)<br/> | (0, 2, 3)<br/> | ||
|} | |} | ||
| + | |||
| + | |||
| + | === Задание 3. Поиск касательных к выпуклому полигону === | ||
| + | |||
| + | На входе выпуклый полигон закрученный против часовой стрелки, заданный как обычно: т.е. число вершин n на первой строке и затем n строк вида (x, y), где x, y -- целые и |x|, |y| <= 10^5. Далее во входном потоке идет строка c числом запросов m и m строк с запросами, т.е. точками вне полигона, из которых мы хотим построить касательные. На выходе ожидается m строк с парами индексов вершин, в которых происходит касание (в литературе иногда эти вершины называются основаниями опорных прямых). Если касательная проходит через сторону полигона, в ответ выдавать индекс той вершины, которая ближе к точке запроса. | ||
| + | Один запрос должен обрабатываться за O(log n). | ||
| + | |||
| + | {| border=1 cellspacing=0 cellpadding=5px width=200px | ||
| + | |- | ||
| + | ! input | ||
| + | ! output | ||
| + | |- valign="top" padding=5 | ||
| + | | | ||
| + | 4<br/> | ||
| + | (0, 0)<br/> | ||
| + | (1, 0)<br/> | ||
| + | (1, 1)<br/> | ||
| + | (0, 1)<br/> | ||
| + | 2<br/> | ||
| + | (2, -1)<br/> | ||
| + | (-2, 0)<br/> | ||
| + | | | ||
| + | 0 2<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/> | ||
| + | |} | ||
| + | |||
| + | |||
| + | [[Category:6 курс. Осень 2014]] | ||
Текущая версия на 12:49, 15 февраля 2015
Лектор - Андрей Давыдов 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 |
yes |
Задание 2. Триангуляция монотонного полигона
Дедлайн: 1.10
На вход полигон в том же формате и с теми же ограничениями на координаты, что в первом задании. Гарантируется, что полигон монотонен относительно OX, закручен против часовой стрелки, и первая вершина в инпуте — самая левая. Требуется разбить его на треугольники. На выходе N-2 тройки индексов (номеров вершин полигона) — треугольники на соответствующих вершинах. Формат троек такой же как точек в инпуте, то есть (i, j, k). Треугольники должны быть закручены против часовой стрелки, среди возможных троек представляющих один и тот же треугольник нужно выбирать наименьшую лексикографически. Сами тройки могут идти в любом порядке. Вершины полигона нумеруются с 0.
Пример (неофициальный):
| input | output |
|---|---|
|
4 |
(0, 1, 2) |
Задание 3. Поиск касательных к выпуклому полигону
На входе выпуклый полигон закрученный против часовой стрелки, заданный как обычно: т.е. число вершин n на первой строке и затем n строк вида (x, y), где x, y -- целые и |x|, |y| <= 10^5. Далее во входном потоке идет строка c числом запросов m и m строк с запросами, т.е. точками вне полигона, из которых мы хотим построить касательные. На выходе ожидается m строк с парами индексов вершин, в которых происходит касание (в литературе иногда эти вершины называются основаниями опорных прямых). Если касательная проходит через сторону полигона, в ответ выдавать индекс той вершины, которая ближе к точке запроса. Один запрос должен обрабатываться за O(log n).
| input | output |
|---|---|
|
4 |
0 2 |
Задание 4. 2d-tree
Дано множество точек. Запрос — прямоугольник со сторонами параллельными осям координат, ответ — количество точек которые попадают в прямоугольник. Для реализации использовать 2d-tree, прямоугольник считать замкнутым (считается, что точки на границе входят в него).
Формат инпута: на первой строке n - число точек, далее n строк с точками в обычном формате. На следующей строке m - число запросов, далее m строк с запросами в формате x1 x2 y1 y2 — прямоугольник .
Вывести m строк с ответами на каждый запрос.
Пример (неофициальный):
| input | output |
|---|---|
|
4 |
2 |
