ZJOI 2008 瞭望塔三分法

2019-11-10 19:53:05

字體：大中小

供稿：網(wǎng)友

題目鏈接：bzoj點(diǎn)我:-) 洛谷點(diǎn)我:-)

題目描述：致力于建設(shè)全國(guó)示范和諧小村莊的H村村長(zhǎng)dadzhi，決定在村中建立一個(gè)瞭望塔，以此加強(qiáng)村中的治安。我們將H村抽象為一維的輪廓。如下圖所示這里寫(xiě)圖片描述我們可以用一條山的上方輪廓折線(x1, y1), (x2, y2), …. (xn, yn)來(lái)描述H村的形狀，這里x1 < x2 < …< xn。瞭望塔可以建造在[x1, xn]間的任意位置, 但必須滿足從瞭望塔的頂端可以看到H村的任意位置。可見(jiàn)在不同的位置建造瞭望塔，所需要建造的高度是不同的。為了節(jié)省開(kāi)支，dadzhi村長(zhǎng)希望建造的塔高度盡可能小。請(qǐng)你寫(xiě)一個(gè)程序，幫助dadzhi村長(zhǎng)計(jì)算塔的最小高度。

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

輸出格式：輸出文件tower.out僅包含一個(gè)實(shí)數(shù)，為塔的最小高度，精確到小數(shù)點(diǎn)后三位。

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

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

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

感想：三分真神奇。。但是。還是要碼一碼半平面交的。。畢竟。。沒(méi)寫(xiě)過(guò)。。

代碼：

//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;