1719 測資加強 已 rejudge
1049 . E.奶油蛋糕切切切
TopCoder
Tags
Description
奕奕剛過完他的二十三歲生日。在生日那天他收到了一個正方形的生日蛋糕。在他要切蛋糕的時候忽然想到，如果他隨便切幾刀的話，會將蛋糕切成幾塊呢？
奕奕很快地把這個問題換成數學的問題：「給定一個正方形ABCD，還有n條線段，這些線段可以將此正方形分成幾塊區域？」由於奕奕程式不好，所以他希望你能寫一個程式來解決這個問題。
為了簡化問題，對於正方形ABCD，設點A, B, C, D的坐標分別為(0,0), (1,0), (1,1), (0,1) ，也就是每一塊蛋糕的大小是固定的。我們還可以假設每條線段的兩個端點，都一定落在邊AB, BC, CD, DA的其中兩邊，且兩端點不會在同一條邊上（也就是線段不會跟正方形的邊重合），且任兩線段不會重合。如下圖，這三條線段可以將正方形分成七塊：
Input Format
輸入檔包含了多筆的測試資料。每筆測試資料的第一行為一個正整數n (0 < n <= 100)，代表線段的個數。接下來的n行，每一行都有四個浮點數a b c d（都介於0和1之間），用一個以上的空白隔開，各代表著一條線段的兩個端點的坐標：(a,b) 和 (c,d)。一筆測試資料就包含這一共n+1行的輸入。
輸入檔以n=0作為結束，你的程式不需要也不能處理這一行輸入。
Output Format
對於每一筆測試資料，請輸出一個整數c，代表給定的n條線段能將正方形分成幾塊區域。每一行輸出恰好一組測試資料的答案。
Sample Input 1
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
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
Sample Output 1
3
7
8
7
8
Hints
Problem Source
原TIOJ1049 / NPSC2003決賽(prob E)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 50 |
| 2 | 1 | 50 |