Комментарии 40
Школьные задачи все. Ну разве что формула Пика не у всех бывает.
Немного сумбурно. Перескоки с одной тему на другую, но все равно плюс вам старания :) Математика всем нужна.
А что, интересные простенькие задачки с элегантными решениями. Интересно было читать, спасибо за статью!
Был бы в восторге, если так же подробно рассмотрели кривые Безье: как «пройти» такой кривой без изломов через ряд точек, например.
Еще можно почитать статьи Е.В.Андреевой «Вычислительная геометрия на плоскости».
> Отрезок, для которого указано, какой из его концов считается началом, а какой — концом, называется вектором.
Bullshit. Это направленный отрезок. Вектор — это множество сонаправленных отрезков одинаковой длины.
Ну и очередное разжевывание стандартных вещей.
Bullshit. Это направленный отрезок. Вектор — это множество сонаправленных отрезков одинаковой длины.
Ну и очередное разжевывание стандартных вещей.
Последняя задача интересная. Остальные все довольно тривиальны.
n = 33, 5 – 7, 5 +1 = 27Рекомендую не отбивать пробелом дробную часть, а писать вот так:
n = 33,5 – 7,5 +1 = 27Иначе это похоже на перечисление отдельных формул (n = 33; 5 – 7; 5 + 1 = 27) и выносит мозг.
Я — призер городских оллимпиад по программированию (решал комбинаторику, реализацию, геометрию). Но я в упор (учусь только в 7 классе) не могу понять как найти площадь пересечения окружностей.
Была задача просто на acmp — про фонарики. Мне ее дали как «подумать на досуге», я подумал и рассмотрел все случаи.
Кто-либо из присутствующих сможет подсказать как зная координаты центров и радиусы кругов — найти S пересечения.
Была задача просто на acmp — про фонарики. Мне ее дали как «подумать на досуге», я подумал и рассмотрел все случаи.
Кто-либо из присутствующих сможет подсказать как зная координаты центров и радиусы кругов — найти S пересечения.
Написал нечаянно ниже. Насколько я помню (это было оочень давно), это делалось как-то так: пересечь все окружности друг с другом, затем отсортировать точки пересечений по x, затем по y (если x совпадают). Потом идем слева направо так называемой «выметающей» прямой (воображаемая вертикальная пряма(суммируя и вычитая различные части пересечений окружностей). Вроде, как-то так)
Методом Монте-Карло можно. Единственный алгоритм, который помню со времен информатики в школе, но приложить его можно к чему угодно.
Как сумму двух сегментов.
Это если границы пересекаются.
Остальные случаи тривиальны.
Это если границы пересекаются.
Остальные случаи тривиальны.
Точный метод вычисления (как сумма двух сегментов кругов) — да, так решать можно, но будет куча подводных камней.
Но есть такой простой приближённый алгоритм: заменить каждую окружность правильным многоугольником с большим числом вершин (например, сто тысяч), а потом пересечь эти два многоугольника (это делать попроще, чем пересекать круги). При ограничениях, как на acmp, я верю, что может быть достаточно и нескольких тысяч вершин (тогда пересечение многоугольников можно написать за квадрат, что вообще занимает несколько строчек). Добавлю, что, чтобы точность этого приближенного алгоритма была выше, при замене окружности на многоугольник мы делаем его чуть большего радиуса: ровно настолько, чтобы площадь многоугольника была равна площади круга (если немного подумать, можно вывести формулу нового радиуса).
Но есть такой простой приближённый алгоритм: заменить каждую окружность правильным многоугольником с большим числом вершин (например, сто тысяч), а потом пересечь эти два многоугольника (это делать попроще, чем пересекать круги). При ограничениях, как на acmp, я верю, что может быть достаточно и нескольких тысяч вершин (тогда пересечение многоугольников можно написать за квадрат, что вообще занимает несколько строчек). Добавлю, что, чтобы точность этого приближенного алгоритма была выше, при замене окружности на многоугольник мы делаем его чуть большего радиуса: ровно настолько, чтобы площадь многоугольника была равна площади круга (если немного подумать, можно вывести формулу нового радиуса).
Для вычисления площади плоских фигур можно использовать численный «метод ячеек» — разбить область на квадраты или прямоугольные ячейки. Что делать с граничными ячейками — (1) можно истинную границу заменить хордой. (2) Можно вообще граничные ячейки не учитывать.
Если вы упорно хотите посчитать, площадь фигуры ограниченной кусочно непреррывными кривыми аналитическим методом — то замечательным инструментов для этого служит использование формулы Грина для многосвязной области. Она позволит вам посчитать площадь лоской области (с внутренними дырками) и изучается в курсе «Кратные и криволиненйые интегралы». См. «VII Гаврилов Иванова Морозова Кратные и криволинейные интегралы.Элементы теории поля», изд-во МГТУ им Н.Э.Баумана, стр. 295
Если вы упорно хотите посчитать, площадь фигуры ограниченной кусочно непреррывными кривыми аналитическим методом — то замечательным инструментов для этого служит использование формулы Грина для многосвязной области. Она позволит вам посчитать площадь лоской области (с внутренними дырками) и изучается в курсе «Кратные и криволиненйые интегралы». См. «VII Гаврилов Иванова Морозова Кратные и криволинейные интегралы.Элементы теории поля», изд-во МГТУ им Н.Э.Баумана, стр. 295
Насколько я помню (это было оочень давно), это делалось как-то так: пересечь все окружности друг с другом, затем отсортировать точки пересечений по x, затем по y (если x совпадают). Потом идем слева направо так называемой «выметающей» прямой (воображаемая вертикальная пряма(суммируя и вычитая различные части пересечений окружностей). Вроде, как-то так)
Разбейте задачу на подзадачи:
1. Окружности равного радиуса (R=R).
2. Окружности разного диаметра (R>r).
Пусть расстояние между центрами равно D, а также d=D/2 (понадобится при расчетах).
1.1. D>2R (не пересекаются, S=0).
1.2. D=2R (пересекаются в одной точке, S=0).
1.3. D>R (две точки пересечения, строим между ними хорду, считаем площадь сектора, вычитаем площадь треугольника).
1.4. D=R
1.5. D=0
Далее для R и r, только стоит учесть что для меньшей окружности сектор может быть больше 180 грудусов, начиная с момента, когда центр лежит на хорде: D^2 < R^2-r^2
дальше сами…
1. Окружности равного радиуса (R=R).
2. Окружности разного диаметра (R>r).
Пусть расстояние между центрами равно D, а также d=D/2 (понадобится при расчетах).
1.1. D>2R (не пересекаются, S=0).
1.2. D=2R (пересекаются в одной точке, S=0).
1.3. D>R (две точки пересечения, строим между ними хорду, считаем площадь сектора, вычитаем площадь треугольника).
1.4. D=R
1.5. D=0
Далее для R и r, только стоит учесть что для меньшей окружности сектор может быть больше 180 грудусов, начиная с момента, когда центр лежит на хорде: D^2 < R^2-r^2
дальше сами…
Спасибо, все очень понятно!
Многие задачи были в программировании курсе на первом или втором, но неточности решения иногда были, как например во второй задаче. А так интересно, спасибо.
Был призером олимпиад, но, из-за пробелов в вычислительной геометрии так дальше республики и не попал никуда. Спасибо огромное за статью. С нетерпением жду следующую часть.
3) Треугольник задан своими сторонами. Определить тип треугольника: тупоугольный, прямоугольный или остроугольный.
Берем квадрат самой длинной стороны и сравниваем его с суммой квадратов коротких сторон. Если больше — тупоугольный. Если меньше — остроугольный. Если равно — теорема Пифагора. Особенные случаи — по желанию (в условии написано — треугольник «задан», значит все-таки существует). И не надо считать синусы-косинусы совсем.
Берем квадрат самой длинной стороны и сравниваем его с суммой квадратов коротких сторон. Если больше — тупоугольный. Если меньше — остроугольный. Если равно — теорема Пифагора. Особенные случаи — по желанию (в условии написано — треугольник «задан», значит все-таки существует). И не надо считать синусы-косинусы совсем.
Я что-то совсем забыл геометрию…
На рисунке cs403223.userapi.com/v403223083/152c/juz1bZwf7CY.jpg указан отрезок и подписано, что он равен |A|*|B|*cosθ Но мне почему то кажется, что длина этого отрезка равна |A|*cosθ
На рисунке cs403223.userapi.com/v403223083/152c/juz1bZwf7CY.jpg указан отрезок и подписано, что он равен |A|*|B|*cosθ Но мне почему то кажется, что длина этого отрезка равна |A|*cosθ
Да ты прав длинна этого отрезка равна |A|*cosθ. Я просто хотел показать чему равно скалярное произведение этих векторов.
upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Dot_Product.svg/200px-Dot_Product.svg.png
upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Dot_Product.svg/200px-Dot_Product.svg.png
Скалярное произведение вводится для определения угла между векторами. То есть по нему можно сказать ортогональны ли вектора и т.д.
Странно, что никто не отметил, что в решении задачи о выпуклом-невыпуклом многоугольнике заложена скрытая «бомба»: указанный в статье критерий может сказать «выпуклый» для самопересекающегося многоугольника. Поэтому, если задача стоит так: «дана последовательность точек, проверить, образует ли она границу валидного выпуклого многоугольника», то этот алгоритм «спалится».
Хабр расстраивает — 70 плюсов за школьную математику.
Не совсем понял задачу 7 решение методом площадей: «Этот метод не очень хороший. Поскольку здесь используются сравнение чисел с плавающей точкой»
Почему в этом методе нужно сравнивать числа с плавающей точкой?
Почему в этом методе нужно сравнивать числа с плавающей точкой?
Задача 9 - критерий в решении не является достаточным (например, ему звезда удовлетворяет), ещё надо проверить отсутствие самопересечений.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Вычислительная геометрия, или как я стал заниматься олимпиадным программированием.Часть 1