二分|二分-牛客寒假集训营5-B-牛牛战队的比赛地 acm竞赛|算法|c++|二分法

二分-牛客寒假集训营5-D-牛牛与牛妹的约会题目：

文章图片

题意：
输入直角坐标系中 N 个点的坐标 x i , y i ，求 N 个点 v 1 , v 2 , . . . , v N 中任一点到达 X 轴上某定点距离的最大值，输出这些最大值当中的最小值。输入直角坐标系中N个点的坐标x_i,y_i，求N个点v_1,v_2,...,v_N中任一点到达X轴上某定点距离的最大值，\\输出这些最大值当中的最小值。输入直角坐标系中N个点的坐标xi?,yi?，求N个点v1?,v2?,...,vN?中任一点到达X轴上某定点距离的最大值，输出这些最大值当中的最小值。
样例中，三个点到点 ( x , 0 ) 的距离分别是 ∣ x ∣ 、 ∣ 2 ? x ∣ 、 ( x ? 0 ) 2 + ( 0 ? 2 ) 2 = x 2 + 4 \\样例中，三个点到点(x,0)的距离分别是|x|、|2-x|、\sqrt{(x-0)^2+(0-2)^2}=\sqrt{x^2+4} 样例中，三个点到点(x,0)的距离分别是∣x∣、∣2?x∣、(x?0)2+(0?2)2 ?=x2+4 ?
容易发现 , 当 x > = 0 时， x 2 + 4 > = x 2 + 4 ? 4 x = ( 2 ? x ) 2 = ∣ 2 ? x ∣ , 且 x 2 + 4 > x 2 = ∣ x ∣ , 容易发现,当x>=0时，\sqrt{x^2+4}>=\sqrt{x^2+4-4x}=\sqrt{(2-x)^2}=|2-x|,且\sqrt{x^2+4}>\sqrt{x^2}=|x|, 容易发现,当x>=0时，x2+4 ?>=x2+4?4x ?=(2?x)2 ?=∣2?x∣,且x2+4 ?>x2 ?=∣x∣,
因此，当 x > = 0 时， 3 个点到 X 轴上的点 ( x , 0 ) 的最大距离是点 ( 0 , 2 ) 到 ( x , 0 ) 的距离 x 2 + 4 > = 2 。因此，当x>=0时，3个点到X轴上的点(x,0)的最大距离是点(0,2)到(x,0)的距离\sqrt{x^2+4}>=2。因此，当x>=0时，3个点到X轴上的点(x,0)的最大距离是点(0,2)到(x,0)的距离x2+4 ?>=2。
对 x < 0 时， ∣ x ∣ < x 2 + 4 < x 2 + 4 ? 4 x = ∣ 2 ? x ∣ , 最大值是点 ( 2 , 0 ) 到点 ( x , 0 ) 的距离 ∣ 2 ? x ∣ > 2 。对x<0时，|x|<\sqrt{x^2+4}<\sqrt{x^2+4-4x}=|2-x|,最大值是点(2,0)到点(x,0)的距离|2-x|>2。对x<0时，∣x∣2。
所以距离最大值的最小值是 2 ，在点 ( 0 , 0 ) 处取得。所以距离最大值的最小值是2，在点(0,0)处取得。所以距离最大值的最小值是2，在点(0,0)处取得。
题解：
目标就是找到所有点到 X 轴某一点最大值的最小值。目标就是找到所有点到X轴某一点最大值的最小值。目标就是找到所有点到X轴某一点最大值的最小值。
结合数据范围应该是个 O ( N l o g 2 N ) 的做法 , 又因为点在 X 轴上 , 且要求最小值，考虑二分法。结合数据范围应该是个O(Nlog_2N)的做法,又因为点在X轴上,且要求最小值，考虑二分法。结合数据范围应该是个O(Nlog2?N)的做法,又因为点在X轴上,且要求最小值，考虑二分法。
接着是判断条件的选取，若考虑二分最终答案 — — 最小值，那么由于点的未知，无法计算各点到 X 轴上点的距离。接着是判断条件的选取，若考虑二分最终答案——最小值，那么由于点的未知，无法计算各点到X轴上点的距离。接着是判断条件的选取，若考虑二分最终答案——最小值，那么由于点的未知，无法计算各点到X轴上点的距离。
因此考虑二分取到最小值时 X 轴上的点。因此考虑二分取到最小值时X轴上的点。因此考虑二分取到最小值时X轴上的点。
二分 X 轴上的点 m i d ，每次枚举计算 N 个点到该点距离的最大值，同时 p o s 记录最大值点的下标 i ，二分X轴上的点mid，每次枚举计算N个点到该点距离的最大值，同时pos记录最大值点的下标i，二分X轴上的点mid，每次枚举计算N个点到该点距离的最大值，同时pos记录最大值点的下标i，
r e s 记录这些最大值中的最小值，因为要求最大值中的最小值，所以 m i d 应当靠近 p o s , 使得最大值变小。 res记录这些最大值中的最小值，因为要求最大值中的最小值，所以mid应当靠近pos,使得最大值变小。 res记录这些最大值中的最小值，因为要求最大值中的最小值，所以mid应当靠近pos,使得最大值变小。
若 m i d > = x [ p o s ] ，说明二分的点 m i d 在 p o s 的右边 , 更新 r = m i d ，反之更新 l = m i d ，最后输出答案 r e s 。若mid>=x[pos]，说明二分的点mid在pos的右边,更新r=mid，反之更新l=mid，最后输出答案res。若mid>=x[pos]，说明二分的点mid在pos的右边,更新r=mid，反之更新l=mid，最后输出答案res。
代码：

#include #define ll long long #define inf 0x7fffffff using namespace std; const int maxn=1e5+5; int N; double x[maxn],y[maxn]; double mdis,res=inf,mlx=-1,mrx=1; //这里左端点mlx应当要小于mrx，避免出现二者相等的情况double dis(int a,double b) { return sqrt((x[a]-b)*(x[a]-b)+y[a]*y[a]); }int main() { cin>>N; for(int i=0; i1e-6) { double mid=(l+r)/2; int pos; mdis=0; //要计算每一次的最大值 for(int i=0; i=x[pos]) r=mid; else l=mid; }printf("%.4f\n",res); return 0; }

总结：

实数二分计算 m i d 时不可用l + r > > 1 。实数二分计算mid时不可用 \ l+r>>1。实数二分计算mid时不可用 l+r>>1。
实数二分循环条件不能判l < r ，否则会死循环。实数二分循环条件不能判\ l

补充：
在求二分左右端点的极限 m l x 和 m r x 时，由于存在所有点的横坐标相等的情况，所以 m l x 初始值不能大于 m r x ，否则会出现二者相等的情况。在求二分左右端点的极限mlx和mrx时，由于存在所有点的横坐标相等的情况，所以mlx初始值不能大于mrx，\\否则会出现二者相等的情况。在求二分左右端点的极限mlx和mrx时，由于存在所有点的横坐标相等的情况，所以mlx初始值不能大于mrx，否则会出现二者相等的情况。
【二分|二分-牛客寒假集训营5-B-牛牛战队的比赛地】 事实上不求 m l x 和 m r x ，直接将二分端点 l 和 r 设为数据范围的端点 l = ? 10000 , r = 10000 应当是最简洁方便的。事实上不求mlx和mrx，直接将二分端点l和r设为数据范围的端点l=-10000,r=10000应当是最简洁方便的。事实上不求mlx和mrx，直接将二分端点l和r设为数据范围的端点l=?10000,r=10000应当是最简洁方便的。