Вычислительная геометрия, или как я стал заниматься олимпиадным программированием. Часть 2

[@nldr]

Спасибо. Вы молодец!

[@wAngel]

Это олимпиадное программирование?

[@tguev]

Эти задачи есть в олимпиадном программировании

[@tguev]

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

[@wAngel]

Я так понимаю, как часть другой задачи? Обычно в статьях про олимпиадное программирование приводятся оптимальные решения (алгоритмы) какой-либо задачи или класса задач. Может быть вы можете привести пример какой-нибудь реальной олимпиадной/конкурсной задачи?

Мне, да и многим другим, скорее всего, было бы интересно.

[@tguev]

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

[@wAngel]

На олимпиаде именно по программированию?

[@tguev]

Конечно. просто я не привожу ее формулировки. а они могут быть достаточно изощренными. Вот например
Два соседа-фермера получили во владение по участку в виде круга. Возникло подозрение, что часть территории принадлежит обоим фермерам. Они не стали судиться, а объединились в кооператив, чтобы совместно использовать полученную землю. Какая площадь оказалась в распоряжении кооператива?

[@wAngel]

Отлично! А что вы тут программируете? Какой смысл решать численно задачи, имеющие аналитическое решение?

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

[@wAngel]

Просто сейчас похоже больше на набор примеров из базового курса аналитической геометрии. Где тут вычислительная геометрия и программирование? В чём сложность и «олимпиадность»? Где выбор оптимальных решений?
Большинство подобных задач решаются чисто аналитически.

[@tguev]

Я просто хотел показать, что косое произведение в вычислительной геометрии занимает большое место. Особенно если речь идет о взаимном расположении объектов.

[@wAngel]

Да, но вы назвали пост олипмиадным программированием и поместили его в блог «Алгоритмы». У вас получилась хорошая статья, но я за то, чтобы вещи назывались своими именами.

[@tguev]

Пост называется Вычислительная геометрия, или как я стал заниматься олимпиадным программированием. Часть 2
Дело в том, что я начал заниматься олимпиадным программированием именно с рассмотрения этих самых задач…

[@metar]

Вот это модельные задачи по геометрии с зимней школы в Харькове, а в статье — примитивы, про которые во время контеста не должно быть размышлений, так делать или эдак. Имхо.

[@wAngel]

Вот подобного рода задачи и ожидалось увидеть в статье.

Про снайпера забавно)

[@Mrrl]

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

[@Mrrl]

Про цилиндр интересно. Про арбуз — в задаче не сказано, что плоскости надрезов проходят через центр шара, поэтому, во-первых, ломаная вершинами не определяется, а во-вторых, арбуз, скорее всего, не распадется на две части. А если эту задачу предполагается решать через дефект суммы углов сферического многоугольника — то при чем тут программирование? Разве что показать, что умеешь считать угол между векторами с точностью 7 знаков?

[@metar]

Про арбуз — там же вроде написано, что точки разрезов на сфере появляются путем пересечением луча из центра в точки входных данных. Значит плоскости надрезов через центр проходят?
Насколько помню, задача не была сложной: там чуть ли не пересчет телесных углов искомого куска в итоге — но перерешивать лень, уж извините. :-)

[@Mrrl]

Увы. «Один надрез представляет собой сектор круга, в плоскости которого осуществляется разрез. » — про центр шара ничего не сказано.
Если решать через телесные углы, то может быть и сложно, особенно для тех, кто не помнит, как это легко сделать. Проблема в том, что сферическую геометрию не проходят ни в школе, ни в вузе, она есть только в популярных книжках.

[@DisaDisa]

Наверное пост нужно переименовать в «основы Аналитической геометрии.» У меня в книжке по Ангему это все есть и там не указано что это «Вычислительная геометрия»

А если опустить все школьные теоремы, то нормальный вычгем есть в снипетах на степ3д
steps3d.narod.ru/snippets.html
Ну и на алголисте.

PS: Я вообще не понимаю что тут делают классические задачи из классических учебников. БЕЗ кода и при этом утверждается что это статья именно о вычгеме и олимпиадном программирование.

[@CleverMouse]

Понятно, что если прямая задана своим уравнением ax + by + c = 0, то тут и решать нечего. Достаточно подставить координаты точки в уравнение прямой и проверить чему оно равно. Если больше нуля, то точка находится в верхней полуплоскости, если равна нулю, то точка находится на прямой и если меньше нуля, то точка находится в нижней полуплоскости.

Это работает только в половине случаев. Например, уравнения y = 0 и -y = 0 задают одну и ту же прямую — ось абсцисс — но для второго уравнения верхняя полуплоскость характеризуется тем, что результат подстановки меньше нуля. А для уравнений x = 0 и -x = 0 вообще не определено, какая полуплоскость верхняя, а какая нижняя.
Понятно, что на практике обычно достаточно просто различать две полуплоскости, называя их, к примеру, первой и второй, и для такой постановки ответ из статьи корректен, но формулировка глаз всё же режет.

[@Mrrl]

Не проще ли было сказать, что это работает при b>0 (и только тогда)?

[@tguev]

Точно так же можно сказать и про x = 0 и -x = 0. Просто когда я писал статью я подразумевал что прямая не вырождена в вертикальную или горизонтальную

[@KvanTTT]

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

[@oleg1977]

Задача 6, самый последний вывод: «Итак, для того чтобы отрезки имели общие точки необходимо и достаточно»
Имеется в виду: «Итак, для того чтобы отрезки имели общие точки необходимо и достаточно выполнение ровно одного из приведенных двух условий»?

[@tguev]

Да достаточно только одного из условий