2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Угол в многоугольнике
Сообщение04.07.2016, 08:48 
Аватара пользователя
Есть задача на http://codeforces.com/problemset/problem/1/C, суть которой в следующем: есть три точки, которые являются вершинами правильного n-угольника. Нужно найти минимальную площадь многоугольника, которая возможна. Даны координаты трех точек.
В общем, я пробовал решать поиском минимального косинуса, тем самым находя максимальный угол. Затем брать большую сторону, образующую этот угол, и считать площадь многоугольника с этой стороной и углом. Но что-то не зашло. Видимо, вершина всегда угловая точка.

Кто-то предложил http://codeforces.com/blog/entry/5280?mobile=true, найти угол как $gcd(A, B, C)$ (наиб. общ. делитель) где насколько я понял, A, B, C - это углы в треугольнике, образованном заданными точками. Объяснение такое: ясно, что любые две диагонали, проведенные из одной вершины, образуют угол, кратный углу, проведенному из центра описанной окружности многоугольника (он его называет единичным). То есть в этом случае единичный угол можно посчитать, как $gcd(A, B, C)$. С тем, что кратный я не спорю, но почему gcd только от трех? Не может ли быть, например, $gcd(16, 24, 32) = 8,$ тогда как единичный угол равен 4?
Далее, тоже непонятно. Как мы находим число сторон? Пишет: "Если провести из одной вершины отрезки ко всем $n $ вершинам, то сумма $n$ дуг, на которые опираются углы между отрезками, будет равна $2\pi$, а сумма углов — $\pi$, так как углы вписанные. Отсюда $n = \frac{\pi}{gcd(A, B, C)}$."
Ну тут во-первых наверно, отрезки можно провести к $n-1$ вершине, а во-вторых, откуда это свойство? Из школы такого не помню и в интернете найти не могу. В общем, помогите, кто может!

 
 
 
 Re: Угол в многоугольнике
Сообщение04.07.2016, 09:36 
В данном случае: $A + B = C$. Тогда $gcd(A, B, C) = gcd(A, B)$.
Но смысл $A$, $B$, $C$ вы поняли неправильно.
У вас есть три вершины вписанного многоугольника. По ним восстановите центр описанной окружности. От этого центра проведите радиусы в известные вершины. $A$, $B$, $C$ - это углы между радиусами. Тогда каждый такой угол кратен $\frac{2\pi}{n}$. Вот такое минимальное $n$ вам и надо найти.

 
 
 
 Re: Угол в многоугольнике
Сообщение04.07.2016, 12:51 
Аватара пользователя
slavav, хорошо, пусть так, как вы говорите. Но это не отменяет,
Challenger в сообщении #1135591 писал(а):
С тем, что кратный я не спорю...Не может ли быть, например, $gcd(16, 24, 40) = 8,$ тогда как единичный угол равен 4?

и $n$ нельзя найти однозначно... :-(

 
 
 
 Re: Угол в многоугольнике
Сообщение04.07.2016, 13:17 
Для этого у вас есть условие минимальности площади. При постоянном радиусе меньшую площадь имеет правильный многоугольник с меньшим числом сторон. Следовательно вам надо искать наибольший угол, который делит углы между радиусами.

Пример с 16, 24, 40 мне не понятен. Углы в задаче должны иметь вид $\frac{2k\pi}{m}, k < m$. Обратите внимание, что вы вычисляете $gcd$ двух вещественных чисел. При вычислениях с ограниченной точностью вам придётся использовать ограничение на $n$ из условия задачи.

 
 
 
 Re: Угол в многоугольнике
Сообщение04.07.2016, 17:39 
Извините, что ввёл вас в заблуждение. Строить центр окружности не надо. Углы треугольника на трёх вершинах ровно в два раза меньше соответствующих центральных углов. Действительно можно вычислить $2gcd(\alpha, \beta, \gamma)$. Но у вас снова получится НОД вещественных чисел, который надо будет вычислять с оглядкой на точность.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group