題目出處： ACM-ICPC World Final 2005
題目連結： Zones
題目大意： 給出n個基地台被使用的人數數量，和m個重疊區，問說如果只能蓋realn個，最多能供應幾個用戶使用。
解題方法： 由於n最多只到20，可以暴力枚舉取哪些，然後將重疊區扣掉，找最優解。
代碼如下：
2014年4月18日 星期五
Lots of Sunlight
題目出處： ACM-ICPC World Final 2005
題目連結： Lots of Sunlight
題目大意： 在一個城市裡頭，求給定的大樓的某一層樓，在一整天能照到太陽的時間範圍。或者該層樓不存在。
解題方法： 首先，太陽可以假設為無窮遠的地方升起和降落，因此如果周遭大樓層數比你矮，必定能完整看到日出日落。
針對每一筆詢問，分別檢查左邊和右邊，若大樓最高層數大於等於你，則必須考慮此樓層對你的影響。
因為有給一層樓的高度和大樓寬度和大樓之間的距離，因此可以用atan去求得角度。而取使你仰角最高的大樓作為答案。
注意！題目有敘述，因為照到陽光定義為，需要整面照到，因此由該一面最低點往其他大樓的最高點連出去，才為正確角度。
拿下圖為例，A'影響A，假設一層樓高是2，大樓寬度是7，此兩棟大樓之間寬度是4，則角度為atan((2.0*3)/4)。
代碼如下：
題目連結： Lots of Sunlight
題目大意： 在一個城市裡頭，求給定的大樓的某一層樓，在一整天能照到太陽的時間範圍。或者該層樓不存在。
解題方法： 首先，太陽可以假設為無窮遠的地方升起和降落，因此如果周遭大樓層數比你矮，必定能完整看到日出日落。
針對每一筆詢問，分別檢查左邊和右邊，若大樓最高層數大於等於你，則必須考慮此樓層對你的影響。
因為有給一層樓的高度和大樓寬度和大樓之間的距離，因此可以用atan去求得角度。而取使你仰角最高的大樓作為答案。
注意！題目有敘述，因為照到陽光定義為，需要整面照到，因此由該一面最低點往其他大樓的最高點連出去，才為正確角度。
拿下圖為例，A'影響A，假設一層樓高是2，大樓寬度是7，此兩棟大樓之間寬度是4，則角度為atan((2.0*3)/4)。
代碼如下：
The Great Wall Game
題目出處： ACM-ICPC World Final 2005
題目連結：The Great Wall Game
題目大意：一個n*n的棋盤，有n個石頭，花最少的步數，排出一道牆(水平線，垂直線，或者對角線)。移動一步，是石頭水平或垂直移動一格。
解題方法：總共有n(水平線)+n(垂直線)+2(對角線)種可能，求所有可能的最佳解。
將每顆石頭和每個最終位置編號，列出一個二維陣列，表示每顆石頭到每個點所需的步數(水平差+垂直差)。
即將題目轉換成，n*n矩陣，每一行每一列只挑選一個，求總和最小。
(總和最小方法可參考此網址)
附上代碼：
題目連結：The Great Wall Game
題目大意：一個n*n的棋盤，有n個石頭，花最少的步數，排出一道牆(水平線，垂直線，或者對角線)。移動一步，是石頭水平或垂直移動一格。
解題方法：總共有n(水平線)+n(垂直線)+2(對角線)種可能，求所有可能的最佳解。
將每顆石頭和每個最終位置編號，列出一個二維陣列，表示每顆石頭到每個點所需的步數(水平差+垂直差)。
即將題目轉換成，n*n矩陣，每一行每一列只挑選一個，求總和最小。
(總和最小方法可參考此網址)
附上代碼：
2014年4月5日 星期六
Tree-Lined Streets
第一篇文章就獻給了World Final的題目......，而這題其實沒有想像中的難。
題目出處： ACM-ICPC World Final 2004
題目大意：給出一個小鎮的街道分布 ( 二維座標，且道路均為直線 ) ，要將小鎮綠化，因此要種樹。而種樹有兩個規則：
1. 每一條道路上每50公尺才種一棵 ( 生長空間和花費控制 )
2. 若兩條道路有相交，則距離相交點25公尺內都不能種樹 ( 怕妨礙視線 )
整理題目敘述得知：任兩條道路不會有端點重合，而且不存在三線共交點，精度部分在0.001就可以了。輸出最多能種幾棵樹。
解題方法：模擬所有道路相交情況 ( 紀錄相交的點和道路起點距離 )，對每一線段所有交點的距離排序後，針對每一小段進行計算，用貪心法處理。若可種植範圍為正數 則數量最多為 [ 可種植範圍 / 50 ] + 1 棵 。
代碼如下：
訂閱：
意見 (Atom)