题解范例.DOC

★★★☆☆ 題組：ACM Programming Contest World Finals, 1998 題號：Problem A：Crystal Clear 解題者：黃錦輝 解題日期：1998年7月28日 題意： 可把題意視為在ｘｙ座標圖上，for all ｘ,ｙ＝0,1,2,3,．．．，　　　　　　以（ｘ，ｙ）為圓心，半徑為1/2作無數多個圓。在給定一多邊形後，求在此多邊形內所包函的圓的面積，其中多邊形內所包函的面積計算方式為，若該圓完全落在多邊形內，則完全計算；若該圓圓心落在多邊形邊上，則只計一半；若該圓除了圓心以外，有其他部份跟邊相交，則不於計算（若該圓與邊相切，視為在多邊形內）；若該圓圓心為多邊形上的一頂點，則面積為此一頂點的內角（PS:ｎ 邊形內角和為（n-２）π）。 題意範例： 無（題目上有）。 解法： 從輸入中先求出min(x)、max(x)、min(y)、max(y)，for all (x,y)， min(x)= x = max(x) ＆ min(y) = y = max(y)，儉驗（x,y）為圓心的圓是屬於那一類，再根據題意加以計算。 解法範例： 已知五邊形的頂點分別為(0,2)、(3,5)、(6,3)、(6,0)、(1,0)，所以min(x)=0、max(x)=6、min(y)=0、max(y)=5，經儉驗得（1,2）、(2,1)、(2,2)、(2,3)、(3,1)、(3,2)、(3,3)、(3,4)、(4,1)、(4,2)、(4,3)、(5,1)、(5,2)、(5,3)共十四點所成的單位圓完全落在此五邊形內；（1,4）、(2,0)、(2,5)、(3,0)、(4,0)、(5,0)、(6,1)、(6,2)共八點圓心落在邊上；（1,1）、(4,4)雖落在五邊形內，但卻是圓心沒若在邊上而與邊有相交，不於計算，所以所要求的解為　　　(１４+８/２) * (1/4)π + (5-2)/2 * (1/4)π = 15.315。 討論： 無。 程式： 無。 ★★★☆☆ 題組：ACM Programming Contest World Finals, 1998 題號：Problem B: Flight Planning 解題者：葉韋宏 解題日期：1998年9月13日 題意： 設計一個有關航空飛行的程式,在一次飛行旅程中,至少有一個以上的小行程(leg),舉例來說,有一段旅程是從台北到紐約.途中可能先飛到東京,再轉至夏威夷,其次到洛杉磯,最後才抵達紐約,此段飛行共有四個小行程,即(台北,東京),(東京,夏威夷),(夏威夷,洛杉磯),(洛杉磯,紐約).程式要計算出每段小行程中,飛機的飛行高度,使整個旅程飛機的耗油量為最少. 假設飛機以固定每小時400 knots的飛行速度(airspeed)行進,而最有效的飛行高度為30,000 feet, 此高度飛行的耗油量為每小時2000加侖,若不在30,000 feet的高度飛行,每差1000 feet, 每小時耗油量加10加侖,飛機每爬升1000 feet要消耗50加侖的油,下降則不消耗油.飛機起飛和降落都在0 feet的高度,且飛機爬升或降落都不花費時間.若遇到順風,飛機的速度(airspeed)會增加,若遇到逆風,則飛行速度會減少,舉例來說,如果飛行速度為400 knots,風速為 –35 knots,則飛行速度變為350 knots. 原則上,飛機都以1000 feet倍數的高度飛行,且介於20,000 feet ~ 40,000 feet之間. 題意範例： 假設有一旅程有兩段小行程(leg),每段小行程有三組資料,分別為行程長度, 20,000 feet高度的風速, 40,000 feet高度的風速. 20,000 feet ~ 40,000 feet 之間的風速採線性插值(linear interpolation)的方式,資料表示如下: 2 表示有兩段小行程 1500 –50 50 1000 0 0 解答為第一段飛行高度為35,000 feet,第二段飛行高度為30,000 feet,總共耗油量為13985加侖. Sample Input Output for the Sample Input 2(表示有兩個旅程要計算) Flight 1: 35 30 13985 2 Flight 2:20 30 40 23983 1500 –50 50 1000 0 0 3 1000 50 0 2000 0 20 1800 –50 100 解法： 因需計算飛機