Комментарии 27
Спасибо. Вы молодец!
Это олимпиадное программирование?
Эти задачи есть в олимпиадном программировании
Я так понимаю, как часть другой задачи? Обычно в статьях про олимпиадное программирование приводятся оптимальные решения (алгоритмы) какой-либо задачи или класса задач. Может быть вы можете привести пример какой-нибудь реальной олимпиадной/конкурсной задачи?
Мне, да и многим другим, скорее всего, было бы интересно.
Мне, да и многим другим, скорее всего, было бы интересно.
Ну скажем вот эта задача с определением площади пересекающихся кругов вроде как была на олимпиаде.
На олимпиаде именно по программированию?
Конечно. просто я не привожу ее формулировки. а они могут быть достаточно изощренными. Вот например
Два соседа-фермера получили во владение по участку в виде круга. Возникло подозрение, что часть территории принадлежит обоим фермерам. Они не стали судиться, а объединились в кооператив, чтобы совместно использовать полученную землю. Какая площадь оказалась в распоряжении кооператива?
Два соседа-фермера получили во владение по участку в виде круга. Возникло подозрение, что часть территории принадлежит обоим фермерам. Они не стали судиться, а объединились в кооператив, чтобы совместно использовать полученную землю. Какая площадь оказалась в распоряжении кооператива?
Просто сейчас похоже больше на набор примеров из базового курса аналитической геометрии. Где тут вычислительная геометрия и программирование? В чём сложность и «олимпиадность»? Где выбор оптимальных решений?
Большинство подобных задач решаются чисто аналитически.
Большинство подобных задач решаются чисто аналитически.
Я просто хотел показать, что косое произведение в вычислительной геометрии занимает большое место. Особенно если речь идет о взаимном расположении объектов.
Вот это модельные задачи по геометрии с зимней школы в Харькове, а в статье — примитивы, про которые во время контеста не должно быть размышлений, так делать или эдак. Имхо.
Вот подобного рода задачи и ожидалось увидеть в статье.
Про снайпера забавно)
Про снайпера забавно)
Про цилиндр интересно. Про арбуз — в задаче не сказано, что плоскости надрезов проходят через центр шара, поэтому, во-первых, ломаная вершинами не определяется, а во-вторых, арбуз, скорее всего, не распадется на две части. А если эту задачу предполагается решать через дефект суммы углов сферического многоугольника — то при чем тут программирование? Разве что показать, что умеешь считать угол между векторами с точностью 7 знаков?
Про арбуз — там же вроде написано, что точки разрезов на сфере появляются путем пересечением луча из центра в точки входных данных. Значит плоскости надрезов через центр проходят?
Насколько помню, задача не была сложной: там чуть ли не пересчет телесных углов искомого куска в итоге — но перерешивать лень, уж извините. :-)
Насколько помню, задача не была сложной: там чуть ли не пересчет телесных углов искомого куска в итоге — но перерешивать лень, уж извините. :-)
Увы. «Один надрез представляет собой сектор круга, в плоскости которого осуществляется разрез. » — про центр шара ничего не сказано.
Если решать через телесные углы, то может быть и сложно, особенно для тех, кто не помнит, как это легко сделать. Проблема в том, что сферическую геометрию не проходят ни в школе, ни в вузе, она есть только в популярных книжках.
Если решать через телесные углы, то может быть и сложно, особенно для тех, кто не помнит, как это легко сделать. Проблема в том, что сферическую геометрию не проходят ни в школе, ни в вузе, она есть только в популярных книжках.
Наверное пост нужно переименовать в «основы Аналитической геометрии.» У меня в книжке по Ангему это все есть и там не указано что это «Вычислительная геометрия»
А если опустить все школьные теоремы, то нормальный вычгем есть в снипетах на степ3д
steps3d.narod.ru/snippets.html
Ну и на алголисте.
PS: Я вообще не понимаю что тут делают классические задачи из классических учебников. БЕЗ кода и при этом утверждается что это статья именно о вычгеме и олимпиадном программирование.
А если опустить все школьные теоремы, то нормальный вычгем есть в снипетах на степ3д
steps3d.narod.ru/snippets.html
Ну и на алголисте.
PS: Я вообще не понимаю что тут делают классические задачи из классических учебников. БЕЗ кода и при этом утверждается что это статья именно о вычгеме и олимпиадном программирование.
Понятно, что если прямая задана своим уравнением ax + by + c = 0, то тут и решать нечего. Достаточно подставить координаты точки в уравнение прямой и проверить чему оно равно. Если больше нуля, то точка находится в верхней полуплоскости, если равна нулю, то точка находится на прямой и если меньше нуля, то точка находится в нижней полуплоскости.
Это работает только в половине случаев. Например, уравнения y = 0 и -y = 0 задают одну и ту же прямую — ось абсцисс — но для второго уравнения верхняя полуплоскость характеризуется тем, что результат подстановки меньше нуля. А для уравнений x = 0 и -x = 0 вообще не определено, какая полуплоскость верхняя, а какая нижняя.
Понятно, что на практике обычно достаточно просто различать две полуплоскости, называя их, к примеру, первой и второй, и для такой постановки ответ из статьи корректен, но формулировка глаз всё же режет.
Большинство задач должен уметь решать любой уважающий себя разработчик игр, а олимпиадой тут и не пахнет.
Задача 6, самый последний вывод: «Итак, для того чтобы отрезки имели общие точки необходимо и достаточно»
Имеется в виду: «Итак, для того чтобы отрезки имели общие точки необходимо и достаточно выполнение ровно одного из приведенных двух условий»?
Имеется в виду: «Итак, для того чтобы отрезки имели общие точки необходимо и достаточно выполнение ровно одного из приведенных двух условий»?
Да достаточно только одного из условий
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Вычислительная геометрия, или как я стал заниматься олимпиадным программированием. Часть 2