主題
題目連結：
題目大意：
給定一正整數，代表有多少組測試資料。
每組測試資料第一列給定一正整數 n （1 ≦ n ≦ 13），代表有 n 隻吸管，每隻佔一列輸入。接著 n 列輸入，每列給定四正整數 x1 、 y1 、x2 、 y2 （皆小於 100），代表一隻吸管的兩端點之座標（吸管長度保證大於 0）。
定義兩隻吸管「相連」，代表兩隻吸管互相交叉（碰到也算）或是可以經由其他吸管相連連到。
接著有不定列的輸入，每列給定兩正整數 a 、 b （介於 1 ～ n 之間，當 a ＝ b ＝ 0 時代表本組測試資料結束），試問第 a 隻與第 b 隻吸管有無相連。
範例輸入：
2
7
1 6 3 3
4 6 4 9
4 5 6 7
1 4 3 5
3 5 5 5
5 2 6 3
5 4 7 2
1 4
1 6
3 3
6 7
2 3
1 3
0 0
2
1 1 1 3
1 7 1 5
1 2
1 1
0 0
範例輸出：
CONNECTED
NOT CONNECTED
CONNECTED
CONNECTED
NOT CONNECTED
CONNECTED
NOT CONNECTED
CONNECTED
解題思維：
可以用併查集（Union-Find Set）這個資料結構快速得到兩吸管有無相連。
而判斷兩吸管有無交叉，需要一些幾何學的性質。可以使用叉積（Cross Product）和點積（Dot Product）判斷相交和互碰。詳情參見底下的程式碼。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
