b064: 3. 下界函數
標籤 :
通過比率 : 91% (32 人 / 35 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2007-12-08 07:51

內容

很久以前,兩個喜歡研究數字的數學家發現了一種有趣又實用的數列,稱為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 不會有重疊或相接成為一條線段的情形,
並且輸入資料中也不會有垂直線的存在。

輸入說明
測試資料中圖一(a)和圖一(b)的情形都有可能會出現。測試檔的第一行為一個正整數n (1 ≤ n ≤ 500),代表有 n 個函數。接下來的 n 行,每行會有四個介於 0 到10000 的整數x1、y1、x2、y2,代表一個兩端為 (x1, y1) 和 (x2, y2) 的線段函
數。
輸出說明
輸出下界函數所包含的線段數,每組一行。如圖一(a) 輸出 3,圖一(b) 則
輸出 7。
範例輸入
4
0 100 100 20
0 20 100 80
0 40 100 50
0 70 100 60
5
0 30 50 30
40 20 70 15
10 20 30 40
80 10 120 40
90 0 110 40
範例輸出
3
7
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <1M
提示 :
標籤:
出處:
94學年度全國資訊學科能力競賽


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」