52. EXPLOSION!

0 Judge

Code: 0


題目敘述

熱愛爆裂魔法的惠惠,每天都在精進自己在爆裂魔法上的能力與成就。在施放爆裂魔法時大喊一聲「EXPLOSION!!!」更是大快人心。

最近,有一名不願透漏名字且舉止行為怪異、看起來就像變態的冒險者佐藤和真,告訴她可以到城鎮附近的樹林中,一座看起來像是廢棄的城堡練習爆裂魔法。在他們經過幾次的練習之後,卻發現城堡被可能還住在裡面的魔王軍幹部用魔法隱藏起來了!

不願透漏名字的冒險者和真和惠惠想憑著記憶找出城堡的位置,作為他們隊上的程式設計詩人,你能幫幫他們嗎?

樹林的地盤是一個二維座標平面。和真和惠惠腦海中有一些直線段,線段上的所有點就是城堡可能的所在位置。 他們想透過不停地放爆裂魔法瘋狂轟炸來來找出城堡的位置,但是受限於一天只能放一發爆裂魔法,惠惠只會對所有線段上的整數點放爆裂魔法。 給定所有的直線段的兩端點,請你幫他們找出所有在直線段上的整數點的數量。

保證所有直線段不會平行,也就是說,任兩條直線段最多只會有一個交點。

輸入

第一行有一個整數$n$,表示直線段的數量。 接下來有$n$行,每一行有四個整數$x_1、y_1、x_2、y_2$,$(x_1,y_1)、(x_2,y_2)$為一條直線段的兩端點。 $1\le n\le 10^3,\ -10^6\le x_1,y_1,x_2,y_2\le 10^6$

輸出

輸出所有直線段上的整數點的數量。

Sample I/O

Input

3
3 3 5 1
6 3 0 0
1 2 5 2

Output

10

說明

範例參考下圖:

測資限制

測資 範圍 配分
#1 同範測 20
#2 $1\le n\le 100,\ -10^3\le x_1,y_1,x_2,y_2\le 10^3$ 20
#3 $1\le n\le 10^3,\ -10^3\le x_1,y_1,x_2,y_2\le 10^3$ 20
#4 $1\le n\le 10^3,\ -10^6\le x_1,y_1,x_2,y_2\le 10^6$ 20
#5 $1\le n\le 10^3,\ -10^6\le x_1,y_1,x_2,y_2\le 10^6$ 20

Judge Setting

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 5