題目背景
在 Nescafe27 和 28 中，講述了一支探險隊前往 Nescafe 之塔探險的故事……
當兩位探險隊員以最快的時間把禮物放到每個木箱里之后，精靈們變身為一縷縷金帶似的光，簇簇光芒使探險隊員們睜不開眼睛，待一切平靜下來之后，探險隊員來到了一座宮殿中，玉制的石椅上坐著兩個人，「你們就是……Nescafe 之塔護法中的兩位？」
「是的，我們就是神刀護法 xlk 和飛箭護法 riatre……你們來這里做什么？」
「我們是前來拜訪圣主和四位護法的……」
「如果你們想見圣主和其它兩位護法，你們必須穿過前方的七色彩虹，請隨我來吧……」
題目描述
探險隊員們跟隨兩位護法來到了七色虹前，七色虹，就是平面直角坐標系中赤、橙、黃、綠、青、藍、紫七個半圓，第 \(i\) 座半圓形彩虹的圓心是 \((x_i,0)\)，半徑是 \(r_i\)，半圓上所有點的縱坐標均為非負數，探險隊員可以看做一條豎直的，長度等于身高的線段，線段的底端縱坐標為 \(0\)，最高的一位探險隊員的身高為 \(h\)，
現在探險隊員們要從 \((0,0)\) 穿越七色虹到達 \((x_0,0)\)，穿越七色虹的程序中，探險隊員的整個身體必須始終在至少一個半圓形彩虹的內部，由于彩虹的半徑 \(r_i\) 可能太小了，不足以滿足這個條件，因此兩位護法決定幫助他們把所有彩虹的半徑都增大一個非負實數 \(r\)，探險隊員們想知道，\(r\) 最小是多少呢？
輸入格式
第一行兩個實數 \(h\)、\(x_0\)，表示身高和目的地橫坐標，
接下來七行每行兩個實數 \(x_i\)、\(r_i\)，表示七座半圓形彩虹的圓心和半徑，
輸出格式
輸出最小的 \(r\)，四舍五入保留 \(2\) 位小數，
資料范圍
評測時間限制 \(500\ \textrm{ms}\)，空間限制 \(512\ \textrm{MiB}\)，
對于 \(100\%\) 的資料，\(0\le x_i,x_0\le 10^4\)，\(0<h<100\)，\(1\le i\le 7\)，
分析
我們只有徹底抓住這道題的所有性質，才能比較好地找出適合的演算法，
\(100\ \texttt{pts}\)
根據我們的思考，我們發現以下幾個結論：
- 對于給定的 \(r\)，我們可以在 \(\mathcal{O}(1)\) 的時間內判斷是否合法，
- 答案是單調的，也就是說如果 \(r^\prime\) 是合法的，那么 \(\forall r^{\prime\prime}>r^\prime\) 都是合法的，
根據這幾點性質，我們考慮二分答案，復雜度為 \(\mathcal{O}(\log x_0)\)，常數大約為 \(7\times \log_2 100=40\)，可以通過本題，
Code
// @author 5ab
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
const double EPS = 1e-4; // 防止缺精度多取幾位，
const int max_n = 7; // 顏色數
/*
判斷是否合法的標志：區間合并，判斷 [0, x0] 是否在一個連續區間內，
復雜度是 O(nlogn)，其中 n 是顏色數，這個復雜度實際上是排序的復雜度，
注意不能開始時排序，因為隨著半徑的變化，順序也是有可能變化的，
對于半徑為 r，身高為 h，圓心位于 xi 的園的區間為 [xi-sqrt(r^2-h^2), xi+sqrt(r^2-h^2)]，可以由勾股定理得到，
*/
struct interval
{
double lp, rp;
bool operator<(const interval& it)
{
if (rp != it.rp)
return rp < it.rp;
else
return lp < it.lp;
}
};
/*
變數解釋：
it[i]：第 i 個圓所對應的區間；
rad[i]：第 i 個圓的半徑；
pos[i]：第 i 個圓的位置；
hei：最高身高；
ed：終點坐標，
*/
interval it[max_n];
double rad[max_n], pos[max_n], hei, ed;
bool check(double added)
{
double tmp;
for (int i = 0; i < max_n; i++)
{
tmp = sqrt((rad[i] + added) * (rad[i] + added) - hei * hei);
it[i].lp = pos[i] - tmp;
it[i].rp = pos[i] + tmp;
}
sort(it, it + max_n); // 統計區間并排序
for (int i = max_n - 1; i > 0; i--) // 合并區間
{
if (it[i-1].rp < it[i].lp) // 無法合并了
{
if (it[i].lp <= 0 && it[i].rp >= ed) // 判斷是否包含
return true; // 是的就退出
continue; // 否則繼續
}
if (it[i-1].lp > it[i].lp)
it[i-1].lp = it[i].lp;
it[i-1].rp = it[i].rp; // 合并區間，取較大的左端點
}
if (it[0].lp <= 0 && it[0].rp >= ed)
return true; // 最后一個特判
else
return false; // 沒有被完全包含的區間，r 還不夠大
}
int main()
{
double lb = 0, ub = 10010, mid, ans = -1;
scanf("%lf%lf", &hei, &ed);
for (int i = 0; i < max_n; i++)
scanf("%lf%lf", pos + i, rad + i); // 輸入
while (ub - lb > EPS) // 二分，不解釋
{
mid = (lb + ub) / 2;
if (check(mid))
ans = mid, ub = mid; // 試圖尋找更小的答案
else
lb = mid + EPS; // 一定要加這個 EPS，否則會死回圈
}
printf("%.2lf\n", ans);
return 0;
}
后記
這道題是一道很好的二分答案練手題，如果要練習二分答案可以做一下，
雖然這道題有計算幾何的味道，但仔細想想還是一道二分答案題，
有時，我們不要被其包裝所誤導，真正重要的是其內在法則，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/60088.html
標籤：其他
下一篇：云計算的是什么