2012年12月28日 星期五

866 - Intersecting line segments


在二維座標平面上,一條線段 A 由兩個端點 $A_0=(x_0,y_0)$、$A_1=(x_1,y_1)$ 所構成,而兩條線段 A、B 的交點 (如果有的話),和原本 A、B 的四個點,可以組成四條新的線段。

在圖 1.1 中,交點 P 和線段 B、C 的四個端點一共組成了四條新線段。經過計算所有的交點後,結果總共有五條線段。

圖 1.1 - 線段相交

現在給你一些線段,當你計算出所有可能的交點後,總共會有多少條新線段。

為了簡化這個問題,假設任兩條線段兩端和交點不會出現在端點上。

輸入

輸入一開始有一個正整數,代表接下來測試資料組數,接著會有一行空白行,每組測資間也會有空白行。下面描述了這些測資的格式。

測資第一行包含一個線段的數量 N,接著有 N 行,每行有四個以空白分隔的整數 $x_0$、$y_0$、$x_1$、$y_1$,代表一條線段。

輸出

對於每組測資,每組測資間的輸出以一空白行分隔,輸出格式如下所述。

輸出一個整數,代表計算出所有交點過後線段的數量。

範例輸入

1

5
3 1 3 8
4 1 4 8
2 4 9 4
8 7 5 7
5 6 10 1

範例輸出

11

備註:圖 1.2 對應到上列的範例測資