Внутрішні точки решітки#6247
Точка решітки — це точка в декартовій системі координат, координати якої є цілими числами. Внутрішньою точкою решітки будемо називати точку решітки, яка лежить строго всередині заданого многокутника і не лежить на його межі. Наприклад, на рисунку нижче зображено трикутник із шістьма внутрішніми точками решітки.
Дано три пари координат (x_A, y_A), (x_B, y_B), (x_C, y_C), де кожна координата — невід'ємне ціле число, що не перевищує . Необхідно визначити кількість внутрішніх точок решітки, які знаходяться всередині трикутника з вершинами в даних точках. Якщо точки колінеарні або не утворюють трикутника (тобто його площа дорівнює нулю), виведіть (оскільки внутрішніх точок у такому випадку немає).
Перший рядок містить ціле число (0 \le n \le 255) — кількість тестових випадків. Далі слідує рядків, кожен з яких містить шість невід'ємних цілих чисел, що не перевищують : x_A\ y_A\ x_B\ y_B\ x_C\ y_C. Ці числа відповідають координатам точок (x_A, y_A), (x_B, y_B), (x_C, y_C).
Для кожного тестового випадку виведіть одне ціле число у окремому рядку — кількість внутрішніх точок решітки у відповідному трикутнику.
Приклад 1