TopCoder

矢澤にこ
にっこにっこにー♪ あなたのハートににこにこにー♪ 笑顔届ける矢澤にこにこー♪ にこにーって覚えてラブにこー♪

User's AC Ratio

81.2% (13/16)

Submission's AC Ratio

48.5% (33/68)

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

Sample Output 1

3
7
8

Hints

Problem Source

原TIOJ1049 / NPSC2003決賽(prob E)

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2