TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

100.0% (4/4)

Description

很久以前,兩個喜歡研究數字的數學家發現了一種有趣又實用的數列,稱為Davenport-Schinzel 數列。當一個數列滿足以下3 個條件:

  1. 數列裡的任何一個數字都會小於或等於一個給定的正整數n
  2. 任意兩個相鄰的數字都不會一樣
  3. 數列裡找不到兩個數字會間隔地連續出現s+2 次以上(包含s+2 次)

就稱為 (n, s) Davenport-Schinzel 數列,簡稱 DS(n, s) 數列。例如, (1, 2, 3, 1, 3, 2, 1) 不是一個 DS(3, 3) 數列,當我們從數列中取出 1 和 2 這兩個數字會得到(1, 2, 1, 2, 1),這兩個數字間隔地連續出現了5 次,所以它違反了第3 個條件。
而 (1, 2, 3, 1, 3, 2, 3) 就是一個 DS(3, 3) 數列。
Davenport-Schinzel 數列的性質有許多重要的應用,其中之一就是用來估算一組線性函數 (linear functions) 之下界函數 (lower envelope) 的線段數目。假設f1, f2, …, fn 是一組線性函數,每一個 fi 都代表一條線段,它們的下界函數 L 的定義如下:

L(x) = min{fi(x) | 1 ≤ i ≤ n}

其中 L 的定義域 (domain) 是所有 fi 之定義域的聯集。如果 f1, f2, …, fn的定義域都相同的話,L 會是一個凸包(convex)形狀的連續函數,如圖一(a);否則 L 可能會是斷斷續續的線段,如圖一(b)。請注意,在圖一(b)中x∈(x1, x2)並不包含在L 的定義域中。

利用 Davenport-Schinzel 數列來估算下界函式的線段數,需要很複雜的運算。請你利用電腦程式來幫忙計算一組函數的下界函數包含有多少個線段。在這個問題裏,你可以假設任兩個 fi 和 fj 不會有重疊或相接成為一條線段的情形,並且輸入資料中也不會有垂直線的存在。

Input Format

測試資料中圖一(a)和圖一(b)的情形都有可能會出現。測試檔的第一行為一個正整數n (1 ≤ n ≤ 500),代表有 n 個函數。接下來的n 行,每行會有四個介於0 到10000 的整數x1、y1、x2、y2,代表一個兩端為 (x1, y1) 和 (x2, y2) 的線段函數。

Output Format

輸出下界函數所包含的線段數,每組一行。

如圖一(a) 輸出 3,圖一(b) 則
輸出 7。

Sample Input

輸入範例1:
4
0 100 100 20
0 20 100 80
0 40 100 50
0 70 100 60

輸入範例2:
5
0 30 50 30
40 20 70 15
10 20 30 40
80 10 120 40
90 0 110 40

Sample Output

輸出範例1:
3

輸出範例2:
7

Hints

Problem Source

原TIOJ1148 / 94全國賽(prob 3)。

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB)
0 900 65536
1 900 65536
2 900 65536
3 900 65536
4 900 65536