奕奕剛過完他的二十三歲生日。在生日那天他收到了一個正方形的生日蛋糕。在他要切蛋糕的時候忽然想到,如果他隨便切幾刀的話,會將蛋糕切成幾塊呢?
奕奕很快地把這個問題換成數學的問題:「給定一個正方形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