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