2025北京市赛-E. 布置 WAP

思路讲解

这种方式更稳定，精度更高（其实就是用这种方式过了）

      // 方案二：使用固定迭代次数（100次）进行三分搜索。
      // 这种方法不依赖eps，更稳定，且100次迭代足以保证精度远高于1e-8。
for(int i=0; i<100; ++i){
	DB mid1 = l + (r-l)/3.0; // 推荐用 l + (r-l)/3 的形式，数值上更稳定
	DB mid2 = r - (r-l)/3.0;
	if(fx(mid1) > fx(mid2)){
		l=mid1;
	}else{
		r=mid2;
	}
}
printf("%.11f\n",fx(l));

AC代码

https://codeforces.com/gym/105851/my#

源代码

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9;
constexpr ll mod=static_cast<ll>(1e9)+7;
// 采用固定迭代次数的方案，不再需要eps常量
// constexpr double eps=1e-10;

ll N,M,Q,X[MAXN],Y[MAXN],K,lT,A[MAXN];
/*

*/
inline void init(){
	// 根据需要可以清空X和Y数组，但在您的框架中，每次N都会被重置，
    // 旧数据不会被访问，所以这里为空也可以。
}

inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>X[i]>>Y[i];
	}
	ll a,b,c;
	cin>>a>>b>>c;

	auto fx=[&](DB mid)->DB{
		DB x=mid,y=-(DB)a*x/b-(DB)c/b; // 显式转换一下类型，避免整数除法
		DB mx=0;
		FOR(i,1,N){
            // 直接计算距离的平方，最后再开方，可以减少sqrt的调用次数，稍微快一点
			DB dx = x - X[i];
            DB dy = y - Y[i];
			mx=max(mx, dx*dx + dy*dy);
		}
		return sqrt(mx);
	};

	auto fy=[&](DB mid)->DB{
		DB y=mid,x=-(DB)b*y/a-(DB)c/a; // 显式转换
		DB mx=0;
		FOR(i,1,N){
			DB dx = x - X[i];
            DB dy = y - Y[i];
			mx=max(mx, dx*dx + dy*dy);
		}
		return sqrt(mx);
	};

	DB l=-2e8,r=2e8; // 搜索范围，根据题目数据范围可能需要调整

    // a, b, c 是 ll, 在除法中最好转成 DB
	if(b!=0){
        // 方案二：使用固定迭代次数（100次）进行三分搜索。
        // 这种方法不依赖eps，更稳定，且100次迭代足以保证精度远高于1e-8。
		for(int i=0; i<100; ++i){
			DB mid1 = l + (r-l)/3.0; // 推荐用 l + (r-l)/3 的形式，数值上更稳定
			DB mid2 = r - (r-l)/3.0;
			if(fx(mid1) > fx(mid2)){
				l=mid1;
			}else{
				r=mid2;
			}
		}
		printf("%.11f\n",fx(l));
	}else{
        // 同理，处理直线垂直的情况
		for(int i=0; i<100; ++i){
			DB mid1 = l + (r-l)/3.0;
			DB mid2 = r - (r-l)/3.0;
			if(fy(mid1) > fy(mid2)){
				l=mid1;
			}else{
				r=mid2;
			}
		}
		printf("%.11f\n",fy(l));
	}
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}

心路历程（WA，TLE，MLE……）