10902: Pick-up Sticks ★★☆☆☆ 題組：Problem Set Archive with Online Judge

Presentation on theme: "10902: Pick-up Sticks ★★☆☆☆ 題組：Problem Set Archive with Online Judge"— Presentation transcript:

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

2 題意範例：

3 題意範例：

4 題意範例：

5 題意範例：

6 題意範例：

7 題意範例： 4 1 2 3 4 5 5 2 1 Output : Top sticks: 2, 4, 5. 3

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

9 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

10 第二組 : 交點在 AB 線段上

11 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

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

13 (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) 為一順一逆 就是相交

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

15

16 步驟一 : 判斷 (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  不相交

17 解法範例： 4 4

18 候選線段 : NONE 讀入第一條線段 :

19 候選線段 : 讀入第二條線段 : 計算是否相交 : 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 x =  1 (AB , AD) = 40 x x =  2 (CD , CA) = -195 x 245 – 1083 x -33=  2 (CD , CB) = -195 x -215 – 1083 x 7 =  1 第 9 種情況  交叉

20 候選線段 : 讀入第二條線段 : 計算是否相交 : (AB , AC) =  2 (AB , AD) =  2 (CD , CA) =  2 (CD , CB) =  2 重複執行 最後答案 : 2, 3, 4

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

22 其他解法： 兩條線段 : 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 線段上

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

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

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