牛牛战队的比赛地
题意
由于牛牛战队经常要外出比赛，因此在全国各地建立了很多训练基地，每一个基地都有一个坐标(x,y)
这周末，牛牛队又要出去比赛了，各个比赛的赛点都在x轴上。牛牛战队为了方便比赛，想找一个到达训练基地最大距离最小的地方作为比赛地。
题解
三分法模板题目
三分答案位置
三分法维护mid=l+(r-l)/2;
和midr=mid+(r-mid)/2;
对于极小值 凹函数
如果mid>midr 那么最小值在 mid 到r之间
如果mid<midr 那么最小值在 l 到midr之间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| # include<bits/stdc++.h>
using namespace std;
const double esp=(double)1e-6;
struct Point{
int x,y;
}point[(int)1e5+4];
int n;
double check(double x){
double maxn=0;
for(int i=0;i<n;i++){
double temp=(point[i].y*point[i].y+(point[i].x-x)*(point[i].x-x));
maxn=max(maxn,temp);
}
return sqrt(maxn);
}
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>point[i].x>>point[i].y;
double l=-10000,r=10000;
while(fabs(l-r)>esp){
double mid=l+(r-l)/2;
double midr=mid+(r-mid)/2;
if(check(mid)>check(midr))l=mid;
else r=midr;
}
printf("%.4f\n",check(l));
}
|