Класс

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

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

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

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

Использовалась известная формула (известная мне по крайней мере), согласно которой диагонали выпуклого многоугольника, никакие три из которых не пересекаются в одной точке, делят полигон на C²_n-1 + C⁴_n частей.

Ну, а упрощение выражения - это дело техники.

P.S. Кстати, на MathWorld-е я таки нашел эту формулу и результат упрощения (правда уже сегодня, после того, как вчера сделал это самостоятельно ). Но это даже лучше, лишний раз пошевелить извилинами и вспомнить что-то (даже если не выводить) - тоже полезно...

Эт'конечно. Но помнить формулы (или хотя бы их существование) безусловно не вредно)).

а что если добавим условие что мы вводим и количество проведенных диагоналей в многоугольнике. как в таком случае код изменится?