思路
三分套三分,分别固定横坐标和纵坐标,然后分别三分答案
时间复杂度 $O(nk^2)$
其中$k$是单维度三分所需要的次数,它的上界可求:
因为每次三分缩小了$\frac{1}{3}$的答案区间,相当于剩下了$\frac{2}{3}$的区间,循环终止条件为区间大小小于阈值$1e-7$,所以有,$10000*(\frac{2}{3})^k<1e-7$
C++ 代码
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
struct point{
int x;
int y;
// point(int _x, int _y): x(_x), y(_y){}
};
double get_dis(double x, double y, vector<point> set)
{
double res = 0;
for (auto &i: set){
res += sqrt((i.x - x) * (i.x - x) + (i.y - y) * (i.y - y));
}
return res;
}
double three_divide_y(double x, vector<point> set)
{
double l = 0, r = 10000;
double mid_l, mid_r;
while(r - l > 1e-7){
mid_l = (l + r) / 2.0;
mid_r = (mid_l + r) / 2.0;
if (get_dis(x, mid_l, set) < get_dis(x, mid_r, set)){
r = mid_r;
}else{
l = mid_l;
}
}
return get_dis(x, l, set);
}
double three_divide(vector<point> set)
{
double l = 0, r = 10000;
double mid_l, mid_r;
while(r - l > 1e-7){
mid_l = (l + r) / 2.0;
mid_r = (mid_l + r) / 2.0;
if(three_divide_y(mid_l, set) < three_divide_y(mid_r, set)){
r = mid_r;
}else{
l = mid_l;
}
}
return three_divide_y(l, set);
}
int main()
{
int N;
cin>>N;
vector<point> set;
set.resize(N);
for (int i = 0; i < N; i++){
point p;
cin>>p.x>>p.y;
set[i] = p;
}
cout<<round(three_divide(set))<<endl;
return 0;
}