国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學(xué)院 > 開發(fā)設(shè)計 > 正文

ZJOI 2008 瞭望塔 三分法

2019-11-10 19:53:05
字體:
供稿:網(wǎng)友

題目鏈接:bzoj點我:-) 洛谷點我:-)

題目描述: 致力于建設(shè)全國示范和諧小村莊的H村村長dadzhi,決定在村中建立一個瞭望塔,以此加強村中的治安。 我們將H村抽象為一維的輪廓。如下圖所示 這里寫圖片描述 我們可以用一條山的上方輪廓折線(x1, y1), (x2, y2), …. (xn, yn)來描述H村的形狀,這里x1 < x2 < …< xn。瞭望塔可以建造在[x1, xn]間的任意位置, 但必須滿足從瞭望塔的頂端可以看到H村的任意位置??梢娫诓煌奈恢媒ㄔ觳t望塔,所需要建造的高度是不同的。為了節(jié)省開支,dadzhi村長希望建造的塔高度盡可能小。 請你寫一個程序,幫助dadzhi村長計算塔的最小高度。

輸入格式: 輸入文件tower.in第一行包含一個整數(shù)n,表示輪廓折線的節(jié)點數(shù)目。接下來第一行n個整數(shù), 為x1 ~ xn. 第三行n個整數(shù),為y1 ~ yn。

輸出格式: 輸出文件tower.out僅包含一個實數(shù),為塔的最小高度,精確到小數(shù)點后三位。

思路: 首先,我們發(fā)現(xiàn)把每段輪廓線看作一條直線,那么所有直線左邊的公共部分就是瞭望塔最終應(yīng)該在的位置范圍,樣例如圖: 這里寫圖片描述 想到這里,半平面交可做了。

接下來,考慮兩個相鄰的端點x, x+1,可以發(fā)現(xiàn)它們之間的那一段答案是單峰的,所以用三分法解決即可。 單峰性的證明: 當(dāng)我們討論瞭望塔的位置在 x 和 x+1 之間時 , 這一段區(qū)間上方的瞭望塔區(qū)間一定為一個下凸的單峰,可以分類討論x至x+1的情況,可以發(fā)現(xiàn)不管是上升下降還是平的,答案都是一個單峰

(稍嚴(yán)謹(jǐn)?shù)淖C明:當(dāng)我們討論瞭望塔的位置在 i 和 i+1 之間時 , 其他的直線可以組成一個下凸的半平面 , 將整個圖形旋轉(zhuǎn)使得直線水平 , 可知下凸的半平面仍保持其性質(zhì)。 那么瞭望塔的高度在此線段上保持單峰性)

感想: 三分真神奇。。 但是。還是要碼一碼半平面交的。。畢竟。。沒寫過。。

代碼

//miaomiao 2017.2.8#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>using namespace std;#define For(i, a, b) for(int i = (a); i <= (int)(b); i++)#define N (300+5)#define eps 1e-9int n;double x[N], y[N], ret, len;inline double calc(int i, double xi){ ret = 0, len = y[i]+(y[i+1]-y[i])/(x[i+1]-x[i])*(xi-x[i]); For(j, 1, n){ if(i==j || i+1==j) continue; int a = j+(j<i? 1: -1); double h = y[j]+(y[a]-y[j])/(x[a]-x[j])*(xi-x[j]); ret = max(ret, h-len); } return ret;}int main(){ scanf("%d", &n); For(i, 1, n) scanf("%lf", &x[i]); For(i, 1, n) scanf("%lf", &y[i]); double ans = 1.0*(1e20); For(i, 1, n-1){ double lm, rm, mid, L = x[i], R = x[i+1]; while(fabs(R-L) > eps){ mid = (R-L)/3.0; lm = L+mid, rm = R-mid; if(calc(i, lm) > calc(i, rm)) L = lm; else R = rm; } ans = min(ans, calc(i, L)); } if(n == 1) ans = 0;
發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表
主站蜘蛛池模板: 濮阳县| 池州市| 乐陵市| 洞口县| 马尔康县| 肇东市| 西华县| 洛浦县| 鄂托克前旗| 清水河县| 东源县| 甘南县| 鄂温| 许昌县| 广州市| 西充县| 德保县| 聊城市| 金华市| 突泉县| 华池县| 东安县| 南昌县| 宁强县| 嘉鱼县| 安庆市| 西昌市| 翁牛特旗| 寿光市| 饶平县| 洛扎县| 股票| 舟山市| 宁德市| 武宣县| 托克托县| 景宁| 合山市| 永善县| 大连市| 灵山县|