Pull to refresh

Comments 40

Школьные задачи все. Ну разве что формула Пика не у всех бывает.
Немного сумбурно. Перескоки с одной тему на другую, но все равно плюс вам старания :) Математика всем нужна.
UFO just landed and posted this here
Вроде синусы начинают в 7-8 классе проходить, а автор так вообще на первом курсе это всё делал, как это возможно в 5ом классе?
UFO just landed and posted this here
А что, интересные простенькие задачки с элегантными решениями. Интересно было читать, спасибо за статью!
Был бы в восторге, если так же подробно рассмотрели кривые Безье: как «пройти» такой кривой без изломов через ряд точек, например.
> Отрезок, для которого указано, какой из его концов считается началом, а какой — концом, называется вектором.
Bullshit. Это направленный отрезок. Вектор — это множество сонаправленных отрезков одинаковой длины.
Ну и очередное разжевывание стандартных вещей.
«Вектор — понятие, определяемое в разных разделах математики различно» — говорит нам Википедия.

«Вектор в геометрии — упорядоченная пара точек (или направленный отрезок), одна из которых называется началом, вторая — концом вектор» — утверждает она же.
«Вектор — класс эквивалентности кривых на многообразии», говорит нам дифференциальная геометрия :D
Последняя задача интересная. Остальные все довольно тривиальны.
n = 33, 5 – 7, 5 +1 = 27
Рекомендую не отбивать пробелом дробную часть, а писать вот так:
n = 33,5 – 7,5 +1 = 27
Иначе это похоже на перечисление отдельных формул (n = 33; 5 – 7; 5 + 1 = 27) и выносит мозг.
Я — призер городских оллимпиад по программированию (решал комбинаторику, реализацию, геометрию). Но я в упор (учусь только в 7 классе) не могу понять как найти площадь пересечения окружностей.

Была задача просто на acmp — про фонарики. Мне ее дали как «подумать на досуге», я подумал и рассмотрел все случаи.

Кто-либо из присутствующих сможет подсказать как зная координаты центров и радиусы кругов — найти S пересечения.
Написал нечаянно ниже. Насколько я помню (это было оочень давно), это делалось как-то так: пересечь все окружности друг с другом, затем отсортировать точки пересечений по x, затем по y (если x совпадают). Потом идем слева направо так называемой «выметающей» прямой (воображаемая вертикальная пряма(суммируя и вычитая различные части пересечений окружностей). Вроде, как-то так)
Методом Монте-Карло можно. Единственный алгоритм, который помню со времен информатики в школе, но приложить его можно к чему угодно.
Точность несолидная
Как сумму двух сегментов.
Это если границы пересекаются.
Остальные случаи тривиальны.
Точный метод вычисления (как сумма двух сегментов кругов) — да, так решать можно, но будет куча подводных камней.

Но есть такой простой приближённый алгоритм: заменить каждую окружность правильным многоугольником с большим числом вершин (например, сто тысяч), а потом пересечь эти два многоугольника (это делать попроще, чем пересекать круги). При ограничениях, как на acmp, я верю, что может быть достаточно и нескольких тысяч вершин (тогда пересечение многоугольников можно написать за квадрат, что вообще занимает несколько строчек). Добавлю, что, чтобы точность этого приближенного алгоритма была выше, при замене окружности на многоугольник мы делаем его чуть большего радиуса: ровно настолько, чтобы площадь многоугольника была равна площади круга (если немного подумать, можно вывести формулу нового радиуса).
Для вычисления площади плоских фигур можно использовать численный «метод ячеек» — разбить область на квадраты или прямоугольные ячейки. Что делать с граничными ячейками — (1) можно истинную границу заменить хордой. (2) Можно вообще граничные ячейки не учитывать.

Если вы упорно хотите посчитать, площадь фигуры ограниченной кусочно непреррывными кривыми аналитическим методом — то замечательным инструментов для этого служит использование формулы Грина для многосвязной области. Она позволит вам посчитать площадь лоской области (с внутренними дырками) и изучается в курсе «Кратные и криволиненйые интегралы». См. «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
дальше сами…
Вроде подразумевается, что окружностей не две.
Многие задачи были в программировании курсе на первом или втором, но неточности решения иногда были, как например во второй задаче. А так интересно, спасибо.
Был призером олимпиад, но, из-за пробелов в вычислительной геометрии так дальше республики и не попал никуда. Спасибо огромное за статью. С нетерпением жду следующую часть.
3) Треугольник задан своими сторонами. Определить тип треугольника: тупоугольный, прямоугольный или остроугольный.

Берем квадрат самой длинной стороны и сравниваем его с суммой квадратов коротких сторон. Если больше — тупоугольный. Если меньше — остроугольный. Если равно — теорема Пифагора. Особенные случаи — по желанию (в условии написано — треугольник «задан», значит все-таки существует). И не надо считать синусы-косинусы совсем.
Дочитай решение до конца. Я к этому пришел!
Я что-то совсем забыл геометрию…
На рисунке cs403223.userapi.com/v403223083/152c/juz1bZwf7CY.jpg указан отрезок и подписано, что он равен |A|*|B|*cosθ Но мне почему то кажется, что длина этого отрезка равна |A|*cosθ
Я не понимаю геометрический смысл «прямого» скалярного произведения. Если смысл косого произведения это площадь параллелограмма, то какой смысл у прямого?
Скалярное произведение вводится для определения угла между векторами. То есть по нему можно сказать ортогональны ли вектора и т.д.
Странно, что никто не отметил, что в решении задачи о выпуклом-невыпуклом многоугольнике заложена скрытая «бомба»: указанный в статье критерий может сказать «выпуклый» для самопересекающегося многоугольника. Поэтому, если задача стоит так: «дана последовательность точек, проверить, образует ли она границу валидного выпуклого многоугольника», то этот алгоритм «спалится».
Хабр расстраивает — 70 плюсов за школьную математику.
Не все к сожалению знают школьную математику!
Не совсем понял задачу 7 решение методом площадей: «Этот метод не очень хороший. Поскольку здесь используются сравнение чисел с плавающей точкой»

Почему в этом методе нужно сравнивать числа с плавающей точкой?
Это не метод плохой, это задача сама по себе плохая (недостаточно аккуратно поставленная).
«Точка лежит на границе» — само по себе практически невозможное событие, если координаты заданы с плавающей точкой. В любом случае нужно задавать допустимую точность («эпсилон»).

Задача 9 - критерий в решении не является достаточным (например, ему звезда удовлетворяет), ещё надо проверить отсутствие самопересечений.

Only those users with full accounts are able to leave comments. Log in, please.