Количество точек на границе многоугольника

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

    Количество точек на отрезке с целочисленными координатами равно НОД (dx, dy) + 1. Значит, количество точек на границе многоугольника равно SUM (HOД(dx_i, dy_i) + 1) - n = SUM HOД(dx_i, dy_i).
    НОД - Наименьший Общий Делитель.

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

Листинг C++

long long count_B (vector < point > &p)
{
    int i, j;
    long long count = 0;
    for (i = 0; i < p.size(); ++ i)
    {
        j = (i + 1) % p.size();
        count += gcd (p[j].x - p[i].x, p[j].y - p[i].y);
    }
    return count;
}

16:01
21.07.2009

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