Внутренние точки решетки
Внутренние точки решетки
Точками решетки называются точки на координатной плоскости с целочисленными координатами. Внутренней точкой решетки будем называть точку решетки, лежащую внутри заданного многоугольника, но не на его границе. Например, ниже приведен треугольник с шестью внутренними точками решетки.
Напишите программу, которая считывает три пары координат (xA
, yA
), (xB
, yB
), (xC
, yC
), каждая из которых является беззнаковым целым числом, не большим 100. Числа в строке разделяются одним пробелом и задаются в порядке xA yA xB yB xC yC
. Эти координаты описывают три разные (но возможно коллинеарные) точки решетки. Если точки задают треугольник с ненулевой площадью, то следует вывести количество внутренних точек решетки в треугольнике. Иначе следует вывести ноль (если точки коллинеарны, то внутренние точки решетки отсутствуют).
Входные данные
Начинаются целым числом n (0 ≤ n ≤ 255). Далее следует n тестов. Каждый тест задается списком из шести беззнаковых целых чисел, не превосходящих 100. Шесть целых чисел xA yA xB yB xC yC
соответствуют координатам (xA
, yA
), (xB
, yB
), (xC
, yC
).
Выходные данные
Для каждого теста вывести в отдельной строке количество внутренних точек решетки.
4 0 0 100 0 100 100 0 0 98 100 100 100 0 0 99 100 100 100 0 0 99 99 100 100
4851 49 0 0