2020牛客寒假算法基礎集訓營5：B.牛牛戰隊的比賽地(二分/三分)

整理的算法模闆：ACM算法模闆總結（分類詳細版）

連結：https://ac.nowcoder.com/acm/contest/3006/B

來源：牛客網

題目描述

由于牛牛戰隊經常要外出比賽，是以在全國各地建立了很多訓練基地，每一個基地都有一個坐标(x,y)(x,y)。

這周末，牛牛隊又要出去比賽了，各個比賽的賽點都在xx軸上。牛牛戰隊為了友善比賽，想找一個到達訓練基地最大距離最小的地方作為比賽地。

這個問題對于牛牛戰隊太簡單了，它就交給了你，你來幫他算一下~

輸入描述:

輸入資料第一行包含一個整數N(1 \leq N \leq 100,000)N(1≤N≤100000)，表示牛牛戰隊訓練基地的數量。

接下來NN行，每行包括22個整數x,y(-10,000 \leq x,y \leq 10,000)x,y(−10000≤x,y≤10000)，表示每一個訓練基地的坐标。

輸出描述:

輸出一個小數，表示選擇的比賽地距離各訓練基地最大距離的最小值。

如果你的答案是aa，标準答案是bb，當\frac{|a-b|}{max(1,|b|)}\leq 10^{-4}

max(1,∣b∣)

∣a−b∣

​

≤10

−4

時，你的答案将被判定為正确。

示例1

輸入

複制

3

0 0

2 0

0 2

輸出

複制

2

說明

當在(0,0)(0,0)比賽時，到三個訓練基地的最大距離是22。可以證明這是最小值。

思路：

二分X軸上的點mid，每次枚舉計算N個點到該點距離的最大值，同時pos記錄最大值點的下标i，

res記錄這些最大值中的最小值，因為要求最大值中的最小值，是以mid應當靠近pos,使得最大值變小。

若mid>=x[pos]，說明二分的點mid在pos的右邊,更新r=mid，反之更新l=mid，最後輸出答案res。。

至今有個疑問，我在代碼中第一步找題中所給點的最左端時，用minl=INF來初始化就是錯的，換成0，就對了；搞不懂；

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
struct node
{
	double x,y;
}bb[100005];
double dis(int i,double j)
{
	return sqrt((bb[i].x-j)*(bb[i].x-j)+(bb[i].y)*(bb[i].y));
}
int main()
{
	
	int n;
	cin >>n;
	double minl=0,maxr=-INF;
	for(int i=0;i<n;i++)
	{
		cin >>bb[i].x>>bb[i].y;
		minl=min(minl,bb[i].x),maxr=max(maxr,bb[i].x);
	}
	double l=minl,r=maxr,res,mid,ans=INF;
	while(r-l>1e-6)
	{
		mid=(l+r)/2;
		int pos;
		res=0;
		for(int i=0;i<n;i++)
		{
			if(res<dis(i,mid))
			{
				pos=i;
				res=dis(i,mid);
			}
		}
		ans=min(ans,res);
		if(mid>=bb[pos].x) r=mid;
		else l=mid; 
	}
	printf("%.4f\n",ans);
	
}
           

.

更新一下三分做法，證明他是個凹函數（我也不會證明qaq…官方題解也不說明…）

然後就是三分x，就可以了；

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
typedef long long ll;
double x[N],y[N];
int n;
double check(double res)
{
	double temp=0;
	for(int i=0;i<n;i++)
	{
		double dis=(x[i]-res)*(x[i]-res)+y[i]*y[i];
		if(dis>temp) temp=dis;
	}
	return temp;
}
int main()
{
	cin >>n;
	for(int i=0;i<n;i++) cin >>x[i]>>y[i];
	double l=-10000,r=10000,mid,midd;
	while(fabs(r-l)>1e-6)
	{
		mid=(l+r)/2;
		midd=(mid+r)/2;
		if(check(mid)>check(midd)) l=mid;
		else r=midd;
	}
	printf("%.4lf\n",sqrt(check(l)));
}