92. Intersection of Lines on Integer Points

Intersection of Lines on Integer Points

題目敘述

平面上給定 $n$ 條線，線給出的方式是線上相異兩點，求有幾對兩線之間的交點是整數點，已知任兩條線不平行

我們說一個平面上的點 $(x_i, y_i)$ 是整數點，如果 $x_i, y_i$ 都是整數

請注意是直線而不是線段

輸入

每筆測資只有一個輸入

第一行有一個數字 $n$

接下來有 $n$ 行，每行有四個數字代表兩個平面點 $(x_i, y_i), (w_i, z_i)$ 連成所構成的一條直線

$$ 1 \leq n \leq 2000 $$ $$ |x_i|, |y_i|, |w_i|, |z_i| \leq 10^6 $$

輸出

輸出一個數字代表有幾對兩線之間的交點是整數點

Sample Input

2
0 0 2 2
0 2 2 0

Sample Output

1

Sample Input

5
5 -5 1 0
10 5 -6 -9
5 -3 -3 -8
-5 2 2 -1
2 0 -2 4

Sample Output

2

Note

記得要輸出換行，也就是說輸出程式碼應該是這樣

cout << ans << '\n';

Hint

可以參考講義程式碼（講義有一部分有誤）

https://gist.github.com/rareone/f5af9ee7ef2464e680b7e11c81a3b5cf

Judge Setting

run-time limit: 4000 ms
memory limit: 268435456 byte
測資數量: 7