March 13th, 2010

|, me, hikki, ok

Задачка

В четверг на военке компания увлечённых товарищей поделилась забавной задачкой:
«Доказать или опровергнуть, что у выпуклого многоугольника хотя бы одно ребро лежит на bounding box.»

Для общего случая решить не смог (порвал брутфорсом для треугольника и ромба), но нашёл в интернете, что это утверждение действительно всегда верно и доказано товарищами Freeman и Shapira в «Determining the Minimum Area Encasing Rectangle for an Arbitrary Closed Curve». Хотел было почитать их статью, а за неё везде денег просят. Она, блин, 1975-ого года. Эти буржуи совсем офигели, я считаю. Какая, нафиг, наука, если ничего нахаляву прочитать нельзя? А потом удивляются, что студент дурной пошёл.