«
»

Олимпиадные задачи.

December 11, 2007, 10:23 am

Случайно (не скажу по какому поводу) наткнулся на задачки МФТИ.

Вот собственно эти задачки http://acm.mipt.ru/judge/problems.pl , видно, народ пыхтит, решает.

Смотрим в задачи, которые никто не решил.

Лучшая кластеризация – задача на нахождение палитры классическая, а если ещё результат k-means уточнить, так вообще можно отлично задачу решить.

Планарность графа – тоже стандартная задача на проверку корректности трехмерной модели. Единственное, что каждый многоугольник может тут быть внешней границей, что заставляет всё таки перебор делать.

Мораль сей басни такова – и то и другое графическим программистом из геймдева решается достаточно легко.

Category: Uncategorized  |  Comment (RSS)  |  Trackback
  • IronPeter

    По-моему, критерий планарности графа – это наличие в нем полного четырехвершинника или пятиугольной звездочки. Даже когда был студентом не умел доказывать. Проверять сложно как по мне.

    Или планарность это не то?

  • Balmer

    Планарный граф – это (дефакто) такой, где к одной edge не прилинковано больше двух многоугольников. Тут основной косяк – отличить многоугольник от внешней границы. Но это только перебором можно сделать. Планарность – это возможность разложить граф на плоскости без пересечений edge.

  • IronPeter

    http://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84

    Я про четырехвершинник насвистел конечно. Граф 3-3 или пятивершинник.

  • Balmer

    Ага, верно. Только мне тамошняя терминология не нравится. Куда приятнее топологический формализм – многоугольник, ребро, дырка.

  • IronPeter

    > где к одной edge не прилинковано больше двух многоугольников

    Так книжка с N страничками отлично раскладывается на плоскости. Никак не связаные свойства

  • Balmer

    Книжка с N страницами разложенная на плоскости отлично представляется как N/2 многоугольников, где половина страниц – это дырки, а половина – это заполненные полигоны.

  • IronPeter

    Не понимаю. Как по графу, который задает ту самую книжку с N страничками определить, что он может быть планарным? Есть множество ребер, есть множество вершин. Клади на плоскость, пожалуйста.