【問題L32】奶油蛋糕切切切。 [回頁]

奕奕剛過完他的二十三歲生日。在生日那天他收到了一個正方形的生日蛋糕。在他要切蛋糕的時候忽然想到,如果他隨便切幾刀的話,會將蛋糕切成幾塊呢?

奕奕很快地把這個問題換成數學的問題:「給定一個正方形ABCD,還有n條線段,這些線段可以將此正方形分成幾塊區域?」由於奕奕程式不好,所以他希望你能寫一個程式來解決這個問題。

為了簡化問題,對於正方形ABCD,設點A, B, C, D的坐標分別為(0,0), (1,0), (1,1), (0,1) ,也就是每一塊蛋糕的大小是固定的。我們還可以假設每條線段的兩個端點,都一定落在邊AB, BC, CD, DA的其中兩邊,且兩端點不會在同一條邊上(也就是線段不會跟正方形的邊重合),且任兩線段不會重合。如下圖,這三條線段可以將正方形分成七塊:

輸入檔說明

輸入檔包含了多筆的測試資料。每筆測試資料的第一行為一個正整數n (0 < n =< 100),代表線段的個數。接下來的n行,每一行都有四個浮點數a b c d(都介於0和1之間),用一個以上的空白隔開,各代表著一條線段的兩個端點的坐標:(a,b) 和 (c,d )。一筆測試資料就包含這一共n+1行的輸入。

輸入檔以n=0作為結束,你的程式不需要也不能處理這一行輸入。

輸出檔說明

對於每一筆測試資料,請輸出一個整數c,代表給定的n條線段能將正方形分成幾塊區域。每一行輸出恰好一組測試資料的答案。

範例輸入

2

0.38 0 0.38 1

0.49 1 0.49 0

3

0.45 0 0.34 1

0 0.25 1 0.5

0 0.8 0.9 0

4

0 0 1 1

0 1 1 0

0.5 0 0.5 1

0 0.5 1 0.5

0

範例輸出

3

7

8