Разделение выпуклого многоугольника на равные части

Дан выпуклый многоугольник и число k.
Необходимо разделить наш многоугольник на k равных частей.

    Будем "отламывать" искомые многоугольники от исходного по одиночки. Сначала, нам надо разделить многоугольник в отношении 1:(k-1). Потом 2:(k-2) и так далее. У всех найденных многоугольников будет общая вершина - первая вершина в исходном многоугольнике.

Асимптотика O(n).

P.S. Ниже приведена реализация алгоритма с асимптотикой O(n²).

Листинг C++

void npart_convex (vector < point > v, int k, vector < point > &s)
{
    int i;
    for (i = 1; i < k; ++ i)
        s.push_back (part_convex (v, i, k - i));
}

14:50
22.07.2009

По всем вопросам обращаться: rumterg@gmail.com