Задача с TopCoder Open 2019: разрезаем пирог на шесть частей

[Tsvetik]

По-видимому все линии проходят через центр масс. Первая линия проводится произвольно и делит многоугольник пополам. А две оставшиеся так, чтобы они отсекали треть площади. Но это не точно

[vladimirad]

Центр масс и задачу можно решать для трехмерного случая тоже.

[tuxi]

Если мы про пирог, а не про математику, то зачем делить сразу весь пирог? Будем отрезать по 6 одинаковых кусочков общей площадью меньше, чем половина оставшегося пирога :) Заодно решим вопрос с пирогом любой формы. Лишь бы только у него толщина была одинаковая :)

[roswell]

А в итоге всем достаётся не по куску пирога, а по кучке холодных крошек… )

[MagisterLudi]

Можно размолоть в пыль и взвесить поровну.

Слышал, что так площади сложных фигур определяли: вырезали из картона и взвешивали.

[Tsvetik]

Так химики интегралы берут. Вырезают из тетради график и взвешивают на аналитических весах, а потом взвешивают квадратный сантиметр.

[MagisterLudi]

Да, точно, интегралы. И площадь континентов.

[tuxi]

А нигде не указано, что нельзя сразу съедать :) пока пережевывается предыдущий кусочек, можно отрезать следующие.

[Mingun]

Нож быстро затупится (ограничение на количество разрезов) :)

[usharik]

• Находим центр масс.
• Проводим через него линию под углом 0.
• Вращаем, пока дефект площади (S — (S1+S2)) не изменит знак на противоположный.
• Уточняем положение делением интервала пополам.
• Далее делим половину фигуры в отношение 2/3
• Потом большую часть снова пополам

[BubaVV]

Не уверен, что алгоритм сходится

[usharik]

Я тоже не уверен, но ничего лучшего пока не придумал. Почему-то кажется, что сходимость должна обеспечиваться выпуклостью многоугольника, но это не более чем догадка…
Тут еще вопрос с выбором шага для первичного поиска делящей прямой и с быстрым расчетом площади. Или формула Герона, или какое-то разбиение на треугольники.

Кстати, может авторы статьи если не решение, то пару подсказок выложат?)

[BubaVV]

Еще одна мысль. Можно разбить фигуру на треугольники и заменить каждый на точку с соответствующей массой. И примерно делить на части уже облако точек. Возможно, такая задача будет проще. Окончательно подправить положение прямых уже через расчет по пересекаемому ребру

[orion76]

Есть формула вычисления площади многугольника по координатам:
Формула площади Гаусса (формула землемера или формула шнурования или алгоритм шнурования)

т.е.
1.Можем вычислить площадь всего многоугольника.
2.Площади частей равны и вычисляются из площади исходного многоугольника.

Далее с использованием той же формулы можно составить систему уравнений.

Дополнительные «условия»:
1. Одна вершина («центр» исходной фигуры) «частей»-многоугольников общая.
2.Каждая «часть» имеет одну общую вершину с соседними частями.
3.«Зеркальные» вершины противоположных «частей» через «центр» лежат на одной прямой («линия разреза»).
4.Каждая «линия разреза» делит исходную фигуру на 2 части равной площади.
5.Все вершины частей лежат на ребрах-вершинах исходной фигуры.

Далее ищем-подбираем способ-алгоритм решения системы уравнений с необходимой точностью.

[usharik]

Вот за формулу — спасибо! Не знал про нее. Если что-то подобное узнал, то разговор был начат не зря))

[Ketovdk]

это не правда. Можно доказать при помощи квадрата, верхняя грань которого заменена на дугу, которая содержит очень много точек, но при этом почти вырожденная. Тогда центр масс будет примерно в средине верхней грани.
На самом деле все немного проще: Первую прямую проводим из любой вершины, которая бы делила пополам (можно точно в рациональных), но можно и бинпоиском (или тернарным, но лучше бинарным).
Тут есть два варианта:
1)Потом находим еще одну такую прямую, берем их точку пересечения. Это будет чем-то в духе центра такого, что любая прямая через него делит пополам. (я не уверен, что это правда, но вроде как правда. Если нет, то надежнее писать пункт 2). Далее фиксируем первую прямую, которую мы провели и ищем к ней еще две тем же самым бинпоиском так, чтобы площадь образованных сегментов составляла треть.
2) Вместо того, чтобы центр из пункта один находить пересечением двух прямых, ищем его по первой прямой бинарным поиском по минимальному ответу, образованному тремя прямыми, проходящими через этот центр.
Асимптотика: первая прямая находится за O(N), если по формуле или O(N log(MAXRAD)) бинпоиском. Вторая прямая также. Образуется точка. Еще две прямые, переходящие через эту точку каждая за O(Nlog(MAXRAD))
MAXRAD — это точность угла в радианах. Как видно из асимптотики, без особых зазрений совести ее можно поднимать хоть до 1000 бит

[usharik]

Не очень понял про квадрат и дугу. На положение центра масс не сколько количество, сколько положение точек влияет.

[Ketovdk]

представьте себе квадрат с 4мя вершинами. Центр масс в центре. А теперь замените верхнее ребро на почти вырожденную дугу, которая будет содержать 1000 вершин. Центр масс точек сместится вверх, причем полностью.

[Ketovdk]

Точнее, пусть X и Y будут самыми маленькими и самыми большими из ваших шести областей, вычисленных грейдером. Тогда ваш ответ будет принят, если Y <max (X+10^(-4), X*1+10^(-4)))

Почему неразрешимой? Можно же просто поднять точность до 256 (ну или 128) битового формата и разницы в решении нет никакой

[GarryC]

Легко доказать, что при проведении любых двух линий через центр масс площадь отсекаемых ими кусков одинакова — дальше легко.
Площадь сегмента считает через сумму его треугольников и останется поделить последний треугольник для получения необходимо остатка — тут тригонометрия потребуется.
Ну это, конечно, только идея решения, само решение я за 10 минут не напишу.