2014 dxdy logo

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

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




 
 помогите подсчитать количество пересечений в многоугольнике
Сообщение14.04.2013, 15:25 
Дан выпуклый 20-угольник. никакие 3 его диагонали не имеют общую точку пересечения. найти количество точек пересечения всех диагоналей.

предполагаем , что диагональ может лежать на 2х не соседних точках, даже если эти точки лежат на 1й прямой.

кол-во диагоналей равно $p(n)=C_{n}^2-n$.
Надо подсчитать количество пар этих диагоналей, без повторений и без порядка.
А потом вычесть количество пар, которые не пересекаются.
Для этого надо разделить диагональю многоугольник и подсчитать по обе стороны количество диагоналей. Но это количество зависит от выбранной изначально (режущей)диагонали. И тут я понял, что дальше не знаю что делать.

 
 
 
 Re: помогите подсчитать количество пересечений в многоугольнике
Сообщение14.04.2013, 15:40 
Аватара пользователя
Диагонали не надо даже считать, это только портит. Любая четвёрка вершин - это пересечение, причём одно. Итого $C_n^4$.

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


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