Facebook
From Innocent Porcupine, 4 Years ago, written in Plain Text.
This paste is a reply to Untitled from Queen Lion - go back
Embed
Viewing differences between Untitled and Re: Untitled
#include 
using namespace std;
#define MAX 1000003
#define tiny 0.00000001
000000001
#define pi 3.14
acos(-1)
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 double np=0;//number of person
        for(int i=1;i<=N;i++){
                np+= int (pi*r[i]*r[i]/x);
double (r[i]*r[i]/x);
        }
        if(np >= F+1) (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;
upper=MAX*10,lower=tiny;
        double x;
        while(n--){
                cin>>N>>F;
                for(int i=1;i<=N;i++) cin>>r[i];
                mergeSort(r,1,N);
//mergeSort(r,1,N);
                while(upper - lower > tiny){
                        x=double((upper+lower)/2);
                        if(check(x)) lower=x;
                        else upper=x;
                }
                cout< cout<         }
}