Бісектриси#2623

Бісектриси

1 секунда

64 мегабайти

Складна

Ми всі знаємо, як знаходити рівняння бісектрис у координатній геометрії. Якщо рівняння двох прямих мають вигляд $a_{i} x + b_{i} y + c_{i} = 0$ a_ix + b_iy + c_i = 0 та $a_{j} x + b_{j} y + c_{j} = 0$ a_jx + b_jy + c_j = 0, то визначені й рівняння бісектрис чотирьох кутів, які вони утворюють. Проте потрібно знати, для яких кутів вибирати знак "+" (плюс), а для яких знак "-" (мінус). У цій задачі вам належить зробити аналогічний вибір.

Нехай задано фіксовану точку $(C_{x}, C_{y})$ (C_x, C_y) і $n$ ( $n \leq 10000$ n \leq 10000) інших точок навколо неї. Жодна з цих $n$ точок не розташована на одній прямій із $(C_{x}, C_{y})$ (C_x, C_y). Якщо з'єднати всі ці точки з $(C_{x}, C_{y})$ (C_x, C_y), то отримаємо зіркоподібну топологію з $n$ прямих. Рівняння цих $n$ прямих задані, і саме ці рівняння слід використовувати під час пошуку рівнянь бісектрис. Ці $n$ прямих утворюють загалом $\frac{n ( n - 1 )}{2}$ \frac{n(n-1)}{2} (гострих або тупих) кутів, а отже, існує $\frac{n ( n - 1 )}{2}$ \frac{n(n-1)}{2} бісектрис. Вам треба визначити, для скількох із цих бісектрис рівняння складається із використанням знака "+". На ілюстрації нижче показано випадок для $n = 5$ n=5, $C_{x} = 5$ C_x=5, $C_{y} = 2$ C_y=2. Ця діаграма відповідає єдиному прикладу у вхідних даних.

Вхідні дані

Вхідний файл містить не більше ніж 35 наборів даних. Опис кожного набору наступний:

Перший рядок кожного набору містить три цілі числа $C_{x}$ C_x, $C_{y}$ C_y ( $- 10000 \leq C_{x}, C_{y} \leq 10000$ -10000 \leq C_x, C_y \leq 10000) та $n$ ( $0 \leq n \leq 10000$ 0 \leq n \leq 10000). Кожен із наступних $n$ рядків містить два цілі числа $x_{i}$ x_i, $y_{i}$ y_i ( $- 20000 \leq x_{i}, y_{i} \leq 20000$ -20000 \leq x_i, y_i \leq 20000) і рядок вигляду $a_{i} x + b_{i} y + c_{i} = 0$ a_ix + b_iy + c_i = 0. Тут $(x_{i}, y_{i})$ (x_i, y_i) — точка навколо $(C_{x}, C_{y})$ (C_x, C_y), а рядок задає рівняння прямої, що сполучає $(C_{x}, C_{y})$ (C_x, C_y) та $(x_{i}, y_{i})$ (x_i, y_i). Можна вважати, що $- 100000 \leq a_{i}, b_{i} \leq 100000$ -100000 \leq a_i, b_i \leq 100000 та $- 2000000000 \leq c_{i} \leq 2000000000$ -2000000000 \leq c_i \leq 2000000000. Це рівняння слід використовувати для пошуку рівнянь бісектрис кутів, які утворюють ці прямі.

Введення закінчується набором, де значення $n$ дорівнює нулю.

Вихідні дані

Для кожного набору даних виведіть єдиний рядок. У цьому рядку має міститись одне ціле число $P$ — кількість рівнянь бісектрис, які формуються із використанням знака "+" у рівнянні бісектриси.

Приклади

Приклад 1