Задача 32.
В правильном n-угольнике провели несколько диагоналей, причем никакие три не пересекаются в одной точке. На сколько частей диагонали разбили n-угольник? Диагонали заданы номерами вершин n-угольника,которые они соединяют, все вершины перенумерованы по порядку числами 1, ...,n.
|
Решение задачи 32.
Пусть в фигуре уже проведены L диагоналей, и они разбивают n-угольник на k частей. Проведем еще одну, L+1-ю диагональ. Подсчитаем, сколько ранее проведенных диагоналей пересекает во внутренних точках эта диагональ. Обозначим количество пересечений через S. Проведение диагонали
1) увеличивает количество разбивок n-угольника на 1;
2) каждое пересечение этой диагонали с ранее проведенной диагональю также увеличивает количество разбивок на 1 (по условию никакие 3 диагонали не пересекаются в одной точке).
Итак, после проведения диагонали L+1 количество частей K+S+1 (предполагается, что L+1-я диагональ не совпадает ни с одной ранее проведенной).
Как определить, пересекается ли диагональ, соединяющая вершины i и j, с диагональю, заданной вершинами k и l? Вершины i и j разбивают контур многоугольника на 2 части: множество A - вершины, лежащие на контуре между вершинами i и j, и множество B - вершины контура между j и i (множества A и B не включают i и j). Если K принадлежит одному из этих множеств, а L - другому, то диагонали пересекаются, иначе - нет.
|
