Порожні трикутники#3379

Порожні трикутники

2 секунди

64 мегабайти

Легка

Чи знаєте ви, як легко перетворити дуже просту задачу на надзвичайно складну? Ось приклад. Скільки трикутників можна утворити з $N$ прямих на площині? Якщо всі вони мають різні нахили і жодні три з них не перетинаються в одній точці, то можна утворити максимальну кількість трикутників.

Добре, це не так вже й складно. Але давайте подивимося, що станеться, якщо ми будемо рахувати тільки ті трикутники, які є порожніми (тобто жодна з прямих не проходить через внутрішню частину трикутника). Тоді кількість трикутників раптово зменшується. Наприклад, з $4$ прямими можна утворити лише $2$ порожні трикутники, тоді як загальна кількість трикутників може бути аж $4$ . Зверніться до діаграми.

Насправді, загальна формула для максимальної кількості порожніх трикутників, які можна намалювати за допомогою $N$ прямих, невідома. Однак найскладніше - це знайти правильну конфігурацію прямих. Ваше завдання набагато простіше; маючи $N$ прямих на площині, порахуйте кількість порожніх трикутників.

Вхідні дані

Вхід складається з кількох тестових випадків. Кожен тестовий випадок починається з рядка, що містить ціле число $N$ , $1 \leq N \leq 500$ 1 \le N \le 500, яке вказує на кількість прямих на площині. Наступні $N$ рядків кожен містить чотири цілі числа $x_{1}$ x_1, $y_{1}$ y_1, $x_{2}$ x_2 і $y_{2}$ y_2 (між $- 1000$ і $1000$ ), що представляють пряму, яка проходить через $(x_{1}, y_{1})$ (x_1, y_1) і $(x_{2}, y_{2})$ (x_2, y_2). Гарантується, що жодні три прямі не перетинаються в одній точці, і всі прямі є різними. Вхід завершується рядком з $N = 0$ N = 0.

Вихідні дані

Для кожного тестового випадку виведіть один рядок, що містить кількість порожніх трикутників, утворених даними прямими.

Приклади

Приклад 1