Диагонали многоугольника Опции

[RathaR]

Задача следующая:
В выпуклом многоугольнике который имеет N вершин провели все диагонали, никакие три из них не пересекаются в одной точке. Найти количество частей на которые эти диагонали его розделили.
Задача в числе простых но в голову ничего не лезет...
Подскажите с помощью чего её можна решить?
Ведь зависимость между кол-вом вершин и числом елементов на которые его разбивают диагонали не линейная... Следовательно может быть здесь нужно задействовать рекурсию? или считать пересечения диагоналей? направте на путь истинный

[volvo]

можно и вообще без циклов

WriteLn(trunc((n-1)*(n-2)*(sqr(n)-3*n+12) / 24));

такчто в идеале прийдётся еще работать со строками чтоб получить полный результат %)

Про тип Comp (который может хранить значения от -2⁶³ + 1 до 2⁶³ - 1) не забывай. Тебе емкости этого типа - за глаза хватит, не надо придумывать самому себе проблемы на ровном месте.

[Lapp]

WriteLn(trunc((n-1)*(n-2)*(sqr(n)-3*n+12) / 24));

Класс

RathaR, основная идея моего решения была в том, чтобы смоделировать процесс проведения диагоналей.
Занумеруем вершины многоугольника по порядку (важно, что по порядку). Теперь будем проводить диагонали. Каждая диагональ добавляет к существующей разбивке столько частей, на сколько её делят в настоящий момент (то есть сразу после проведения) другие диагонали. Например, в самом начале первая диагональ добавляет 1 часть к уже существующей 1 части (целый багатокутник), тем самым делая полное число частей равным 2. Вторая диагональ (например, в квадрате), имеющая 1 пересечение (то есть поделенная сама на 2 части) прибавляет 2 части, доводя полное число частей до 4. Можно организовать "проведение диагоналей" с подсчетом точек пересечения. Делаем так..

Проводим диагональ от вершины с номером А к вершине с номером В. Она может пересечь только те диагонали, одна вершина которых (назовем одну из них XY) лежит между А и В (то есть A<X<B), а вторая - вне этой дуги (Y<A or B<Y). Затем, чтобы получить число частей, нужно число пересечений увеличить на 1. Вот и вся идея. Еще раз обращаю внимание, что пересекать нужно только с уже проведенными диагоналями. Выяснить, какие диагонали уже проведены можно, используя порядок проведения. Сначала у меня была идея запоминать это в матрице NxN, но такая матрица слишком велика (по крайней мере для ТР), так что я оставил эту идею (оно и к лучшему)).

В процессе программирования алгоритм претерпел некоторые не меняющие смысла изменения, так что не вполне отражает суть построения.

А как вывести формулу, приведенную volvo, лучше спросить у него самого .

Ну что, RathaR - ты все еще считаешь эту задачу легкой?

Сообщение отредактировано: Lapp - 8.07.2009 9:10

[RathaR]

Ну что, RathaR - ты все еще считаешь эту задачу легкой?

Я - уже нет , а вот организаторы олимпиады наверное всёже считают, раз дают за неё 15 баллов из 400... чем собственно и вводят в заблуждение учасников
Еще раз спасибо за объяснение, сам бы вжизни не справился