10902: Pick-up Sticks ★★☆☆☆ 題組：Problem Set Archive with Online Judge 解題者：陳鈺升 解題日期：2019年3月13日 題意：會有許多組測資，每組會先給定一個正整數 N ，代表有 N 根棍子，接下來會給 N 根棍子的端點座標，我們要算出在最上層的棍子編號共是哪些。 ( N = 0 代表結束 ) ( 依照棍子輸入的順序，編號依序為 1、2、3 … N )

題意範例： 5 1 1 4 2

題意範例： 5 1 1 4 2 2 3 3 1

題意範例： 5 1 1 4 2 2 3 3 1 1 -2.0 8 4

題意範例： 5 1 1 4 2 2 3 3 1 1 -2.0 8 4 1 4 8 2

題意範例： 5 1 1 4 2 2 3 3 1 1 -2.0 8 4 1 4 8 2 3 3 6 -2.0

題意範例： 5 1 1 4 2 2 3 3 1 1 -2.0 8 4 1 4 8 2 3 3 6 -2.0 4 1 2 3 4 5 5 2 1 Output : Top sticks: 2, 4, 5. 3

解法：先看一下 2 線段相交會出現的情況 第一組 : 交點在 CD 線段上

1 2 C C A B B A 4 3 D D D D A B B A C C (AB , AC) (AB , AD) (CD , CA) (CD , CB) 1 逆 正 * 2 3 4

第二組 : 交點在 AB 線段上

5 A 6 B C C D D 8 7 A B A B D D C C B A (AB , AC) (AB , AD) (CD , CA) (CD , CB) 5 正 * 逆 6 7 8

第三組 : 交叉 C 9 A B D (AB , AC) (AB , AD) (CD , CA) (CD , CB) 9 逆 正

(AB , AC) (AB , AD) (CD , CA) (CD , CB) 1 逆 正 * 2 3 4 5 6 7 8 9 規則一 : 只要有一點在線上就是相交 規則二 : (AB,AC) 與 (AB,AD) 為一順一逆且 (CD,CA) 與 (CD,CB) 為一順一逆 就是相交

計算角度 sin<OA,OB> = sin = sin( – ) = sin cos - cos sin     |OA| = | (x1,y1) | = r1 |OB| = | (x2,y2) | = r2

步驟一 : 判斷 (AB , AC) + (AB , AD) 與 (CD , CA) + (CD , CB) 總和 1 逆 正 * -∞ 2 3 4 5 6 7 8 9 3 3 步驟一 : 判斷 (AB , AC) + (AB , AD) 與 (CD , CA) + (CD , CB) 等於 3  相交，不等於 3  不相交 步驟二 : 全部總和小於 0  相交於端點 全部總和大於 0  不相交

解法範例： 4 104.7 73.7 108.7 27.7 108.0 49.2 88.5 157.5 145.7 49.3 143.9 30.0 88.3 9.8 38.5 105.8 4 1047 737 1087 277 1080 492 885 1575 1457 493 1439 300 883 98 385 1058

候選線段 : NONE 讀入第一條線段 : 1047 737 1087 277

候選線段 : 1. 1047 737 1087 277 讀入第二條線段 : 1080 492 885 1575 計算是否相交 : A (1047,737) , B(1087,277) , C (1080, 492 ) , D (885, 1575) AB = (40,-460) , AC = ( 33,-245) , AD = ( -162,838) CD = (-195,1083) , CA = (-33,245) , CB = (7,-215) (AB , AC) = 40 x -245 - -460 x 33 = 5380  1 (AB , AD) = 40 x 838 - -460 x -162 = -41000  2 (CD , CA) = -195 x 245 – 1083 x -33= -12036  2 (CD , CB) = -195 x -215 – 1083 x 7 = 34344  1 第 9 種情況  交叉

候選線段 : 1. 1080 492 885 1575 讀入第二條線段 : 1457 493 1439 300 計算是否相交 : (AB , AC) = -408486  2 (AB , AD) = -351357  2 (CD , CA) = -72743  2 (CD , CB) = -129872  2 重複執行 最後答案 : 2, 3, 4

討論： 在讀取輸入時 ( ex : 123.8 )，可以先讀進一個 integer N ( 123 ) 再將後面的 dot 削掉，在讀近一個整數 P ( 8 ) 這樣我們就可以不需要耗費轉換浮點數的時間 Input = N * 10 + P 測試過後，測資皆只到小數第一位，因此只要將所有 input 放大 10 倍就好

其他解法： 兩條線段 : L1(A,B) , L2(C,D) A ( ax1, ay1 ), B ( ax2, ay2 ), C ( cx1, cy1 ), D ( cx2, cy2 ) 計算2點向量 : Vab = ( av1, av2 ) = ( ax2 – ax1 , ay2 – ay1 ) Vcd = ( cv1, cv2 ) = ( cx2 – cx1 , cy2 – cy1 ) 計算法向量 : Tab = ( at1, at2 ) = ( -av2 , av1 ) Tcd = ( ct1, ct2 ) = ( -cv2 , cv1 ) 計算常數 C1 = ax1 * at1 + ay1 * at2 C2 = cx1 * ct1 + cy1 * ct2 解方程式求焦點 ( X, Y ) Scala = at1 / ct1 Y = (Scala * C1 – C2) / (Scala * at2 – ct2) X = ( C1 – Y * at2 ) / at1 判斷是否在 2 線段上

1. 角度法 : 12 + 4 + 3 = 19 加減法 ， 8 乘除法 ( 整數 ) 2 x 6 1 x 4 2 x 4 3

2. 解方程式 : 4 + 2 + 3 + 8 = 17 加減法 4 + 2 + 6 = 12 乘除法 ( 浮點數 ) 2 x 2 2 x 2 1 x 2 2 2 + 1 2 + 2 + 2 2 x 4

角度 : 0.07 可能需要思考比較久 解方程 : 0.14 浮點數的判斷很惱人 且需要特別判斷水平線或垂直線