на 4 равные по площади части двумя взаимоперпендикулярными линиями

В общем случае не получится.

Ну решает же её народ как-то :) А если торт не делится, можно просто и написать: не делится.

Покопайся тут: http://paulbourke.net/geometry/polygonmesh/

Что-то мне подсказывает, что если найти centroid полигона, то можно будет подумать дальше... (но, может, я и ошибаюсь).

Вот я тоже про центр масс думал. Типа находишь центр масс, предполагаешь, что он есть точка пересечения этих двух перпендикулярных линий. Рисуешь линии, считаешь площадь, если площади не совпадают, крутишь на угол альфа эти линии. Если все ок, то получаешь точку пересечения линий и угол. А вот как это записать кодом я вообще со вчера придумать не могу никак :)

ну всё тупо, а ты троль и курсовик

берёшь первую точку, запоминаешь
берёшь вторую точку — первая и вторые точки образуют грань
нормаль этой грани задаёт первую линию.

потом обходишь по граням и находишь грань у которой нормаль перпендикулярна первой линии — это вторая грань.

потом находишь грань у которой нормаль противоположна первой линии — это третья грань

потом находишь грань у которой нормаль противоположна нормали второй грани — это четвертая грань


каждую из этих граней делишь на 2 и вставляешь по середине точки, ну и соединяешь их как надо через центр

Какое бы направление мы ни взяли, всегда имеется параллельная прямая, делящая фигуру на две части, имеющие равную площадь. Это следует из соображений непрерывности. Будем двигать прямую параллельно себе. Ясно, что существуют два таких положения, при котором часть фигуры «слева» имеет большую площадь, чем часть фигуры «справа», и наоборот. Но тогда существует и такая прямая, для которой площади частей равны. Легко также видеть, что эта прямая единственна: при сдвиге прямой в одну из сторон площадь одной части увеличится, а площадь другой уменьшится.

Проделаем описанную процедуру с произвольно выбранным направлением, а потом и с перпендикулярным ему. Фигура будет разделена на 4 части, площади которых можно обозначить через $%a$%, $%b$%, $%c$%, $%d$%, если обходить вокруг точки по часовой стрелке. По одну сторону от первой прямой находятся части площадью $%a$% и $%b$%, по другую — $%c$% и $%d$%. Отсюда $%a+b=c+d$%.Если рассмотреть вторую прямую, то аналогичным образом выводится равенство $%a+d=b+c$%. Рассматривая полученную систему, мы видим, что $%a=c$%, $%b=d$%. Таким образом, при обходе вокруг точки площади частей будут такие: $%a$%, $%b$%, $%a$%, $%b$%. Здесь также можно заметить, что при заданных направлениях есть ровно одна точка с описанным выше свойством, когда части фигур, расположенные в противоположных четвертях, равны друг другу. Если сдвинуть точку пересечения в одну из четвертей, то в этой четверти площадь уменьшится, а в противоположной — увеличится. Такую точку для заданных направлений далее будем для краткости называть «точкой псевдобаланса».

Рассматривая одну из таких точек, выберем по единичному вектору вдоль каждого из направлений. Пусть это будут векторы $%x$% и $%y$%. Начнём вращать эти направления, чтобы вектор $%x$% постепенно перешёл в вектор $%y$%. Точка псевдобаланса при этом будет, вообще говоря, меняться, двигаясь по непрерывной кривой и возвращаясь в конце в своё исходное положение. Следя за изменяющимся вектором $%x$%, будем сравнивать числа $%a$% и $%b$% — площади фигур, расположенных «влево» и «вправо» от вектора $%x$%. Если изначально эти площади не были равны, то выполнялось неравенство, скажем, $%a > b$%. В процессе движения вектора, роли этих частей поменяются, и фигуры перейдут в фигуры площади $%b < a$%. Поскольку площади меняются непрерывно, из этого следует, что существует какое-то промежуточное положение, при котором площадь части фигуры «слева» от вектора будет равна площади фигуры, расположенной «справа» от него, то есть будет иметь место равенство $%a=b$% для одной из промежуточных точек псевдобаланса. При этом все четыре фигуры станут иметь одинаковые площади.

Какой курсовик? Какой тролль? Кого я троллю?
Я говнокодю сайтики, а в выходные устраиваю себе решение алгоритмических задач. Если кого я и затроллил, то только себя, так как не смог её решить за выходные.

Только не крутить на epsilon-alpha, а подходить на «пол-оборота» — не знаю, как этот метод называется:

Крутим на 45 туда, 45 сюда. Где меньше разница — там нужный сектрор. Дальше опять — 22.5 туда/сюда ... и т.д. до нужного начения.

Гораздо быстрей и точней, чем итеративный подход.

PS: кажись, метод Ньютона... но не ручаюсь.

Это я вроде уже читал. Если не изменяет память, то это то ли 27, то ли 28 задача из какой-то крутой книжки по геометрии.

Методом бисекции?) Интересно, да. А я и не думал про это даже. Только вот опять вопрос, как это записать :)

Вопрос скорее, правильный ли подход, а записать то не проблема.

#define EPS 1e-6

float
area(float alpha)
{
    /* ... */
}

float
find_alpha(float start) {
    float a1 = area(start + start/2);
    float a2 = area(start - start/2);

    if (abs(a1 - a2) < EPS)
        return start;
    else if (a1 < a2)
        return find_alpha(a1);
    else
        return find_alpha(a2);
}

Как-то так, если ничего не путаю.

Спасибо, я буду думать и сюда выкидывать свои мысли :) если у меня получится её записать, то лор будет первое место с решением этой задачки :) Еще раз спасибо :)

Тебе в Job надо. Бесплатно твой курсач тебе никто делать не будет.

convex

насколько я понимаю, ограничение по выпуклости никак не влияет на существование нужного сечения, и его в любом случае можно найти бисекцией.

но для невыпуклого многоугольника становится сложнее написать эффективное решение.

отсюда вопрос - откуда задача, и какие ограничения на входные данные

Ночью подкрадываешься и отрезаешь столько, сколько нужно, ешь, убираешь следы (моешь тарелку и нож) и спать!

Да с чего вы взяли, что это курсовик?! Эта задача на первой странице выдачи гугола. Парень какой-то во втентакали условие написал: https://vk.com/topic-432_30507785
Да и на курсак эта задача не тянет. Больше похоже на РЗ или контрольную на дом :)

Вот отсюда взял задачу: https://vk.com/topic-432_30507785

Циркулем и линейкой. При условии что торт представляет собой круг. Это можно записать аналитически в виде уравнений.

У 2х твоих линий есть точка пересечения, и угол поворота. Вместе это 3 координаты, т.е. ты получаешь 3хмерный вектор. Затем составляешь функцию, которая сопоставит этому вектору показатель суммарной разницы между площадями всех полученных кусков. Дальше применяешь какой-нибудь простой метод оптимизации. Правда сейчас у меня нет уверенности что минимум будет один.

Правда сейчас у меня нет уверенности что минимум будет один

одна из координат - угол наклона, так что минимумы по одной координате будут повторяться с периодом в pi/4.

если многоугольник правильный, то с периодом pi/lcm(4, n)

других повторов быть не должно

будут повторяться с периодом в pi/4.

Ну это мне казалось и так очевидно.

В общем случае не получится.

Всегда получится.