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

[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 13:10

[RathaR]

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

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

[Lapp]

организаторы олимпиады наверное всёже считают, раз дают за неё 15 баллов из 400...

Возможно, они считают эту формулу известной. Но это мне в высшей степени странно.. Я погуглил немного (правда, совсем немного), но не нашел. Интересно, какой способ использовал volvo. Может, все и не так страшно, как я это представил .

[RathaR]

Возможно, они считают эту формулу известной. Но это мне в высшей степени странно.. Я погуглил немного (правда, совсем немного), но не нашел. Интересно, какой способ использовал volvo. Может, все и не так страшно, как я это представил .

Будь я 9 класником который впервые приехал на олимпиаду, и учитывая то, что задания у всех класов одинаковы, я бы с самого начала был бы настроен на то, чтоб попробовать решить первые 2 тоесть самые лёгкие задачи, и убить всё время именно на них, дабы получить хоть какието балы, а не плодить недоделлки по сложным задачам, а увидав бы такие задачи по 15 балов, я бы и дальше смотреть не стал, а розвернулся бы и просто ушол, при том что на математике показываю хорошые показатели, а геометрия мой конёк
То как это трактовать? Как желание организаторов повысить уровень знаний молодёжи, или просто решили забить на 9, да и на 10 класс тоже, мол пусть учатся а в 11 класе будут готовы ко всему...