#include <bits/stdc++.h>
using namespace std;
#define MAX 1000003
#define tiny 0.00000001
#define pi 3.14
int N,F;
int r[MAX];
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] >= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
bool check(double x){
int np=0;//number of person
for(int i=1;i<=N;i++){
np+= int (pi*r[i]*r[i]/x);
}
if(np >= F+1) return true;
else return false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
double upper=MAX,lower=tiny;
double x;
while(n--){
cin>>N>>F;
for(int i=1;i<=N;i++) cin>>r[i];
mergeSort(r,1,N);
while(upper - lower > tiny){
x=double((upper+lower)/2);
if(check(x)) lower=x;
else upper=x;
}
cout<<setprecision(7)<<fixed<<x<<endl;
}
}
Replies to Untitled
Title |
Name |
Language |
UNIX |
When |
Re: Untitled |
Innocent Porcupine |
text |
1587055549 |
4 Years ago. |
{"html5":"htmlmixed","css":"css","javascript":"javascript","php":"php","python":"python","ruby":"ruby","lua":"text\/x-lua","bash":"text\/x-sh","go":"go","c":"text\/x-csrc","cpp":"text\/x-c++src","diff":"diff","latex":"stex","sql":"sql","xml":"xml","apl":"apl","asterisk":"asterisk","c_loadrunner":"text\/x-csrc","c_mac":"text\/x-csrc","coffeescript":"text\/x-coffeescript","csharp":"text\/x-csharp","d":"d","ecmascript":"javascript","erlang":"erlang","groovy":"text\/x-groovy","haskell":"text\/x-haskell","haxe":"text\/x-haxe","html4strict":"htmlmixed","java":"text\/x-java","java5":"text\/x-java","jquery":"javascript","mirc":"mirc","mysql":"sql","ocaml":"text\/x-ocaml","pascal":"text\/x-pascal","perl":"perl","perl6":"perl","plsql":"sql","properties":"text\/x-properties","q":"text\/x-q","scala":"scala","scheme":"text\/x-scheme","tcl":"text\/x-tcl","vb":"text\/x-vb","verilog":"text\/x-verilog","yaml":"text\/x-yaml","z80":"text\/x-z80"}