经典的二分,思路清晰,启发深刻
#include <iostream> #include <fstream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <bitset> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <ctime> #define LL long long #define Vi vector<int> #define Si set<int> #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) #define FU(i,a) for(int i(1); i <= (a); i++) #define FD(i,a) for(int i(a); i >= (1); i--) #define FOR(i,a,b) for(int i(a);i <= (b); i++) #define FORD(i,a,b) for(int i(a);i >= (b); i--) #define SET(a,b) memset(a,b,sizeof(a)) #define SD(a) scanf("%d",&(a)) #define LN printf("\n") #define PS printf(" ") #define pb push_back #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 using namespace std; const double pi = acos(-1.0); const int maxn = 10010; const int INF=99999999; int N,F; double v[maxn]; bool judge(double k){ int num=0; FOR(i,1,N){ num+=int(v[i]/k); if(num>F) return true; } if(num>F) return true; return false; } int main() { int t; SD(t); while(t--){ double sumV=0,left=0.0,right,mid; SD(N);SD(F); int r; FOR(i,1,N){ SD(r); v[i]=pi*r*r; sumV+=v[i]; } right=sumV/F; while((right-left)>1e-7){ mid=(left+right)/2; if(judge(mid)) left=mid; else right=mid; } printf("%.4lf\n",mid); } return 0; }