Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

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

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

    Воспользуемся формулой Пика:

A = I + B/2 - 1

A - площадь многоугольника
I - количество точек внутри многоугольника
B - количество точек на границе многоугольника

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

Листинг C++

long long count_I (vector < point > &p)
{
    return abs (area_polygon (p)) - count_B (p) / 2 + 1;
}


14:25
25.01.2010