Facebook
From Queen Lion, 4 Years ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 171
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 1000003
  4. #define tiny 0.00000001
  5. #define pi 3.14
  6. int N,F;
  7. int r[MAX];
  8. void merge(int arr[], int l, int m, int r)
  9. {
  10.         int i, j, k;
  11.         int n1 = m - l + 1;
  12.         int n2 = r - m;
  13.  
  14.         int L[n1], R[n2];
  15.        
  16.         for (i = 0; i < n1; i++)
  17.                 L[i] = arr[l + i];
  18.         for (j = 0; j < n2; j++)
  19.                 R[j] = arr[m + 1+ j];
  20.         i = 0;
  21.         j = 0;
  22.         k = l;
  23.         while (i < n1 && j < n2)
  24.         {
  25.                 if (L[i] >= R[j])
  26.                 {
  27.                         arr[k] = L[i];
  28.                         i++;
  29.                 }
  30.                 else
  31.                 {
  32.                         arr[k] = R[j];
  33.                         j++;
  34.                 }
  35.                 k++;
  36.         }
  37.  
  38.         while (i < n1)
  39.         {
  40.                 arr[k] = L[i];
  41.                 i++;
  42.                 k++;
  43.         }
  44.  
  45.         while (j < n2)
  46.         {
  47.                 arr[k] = R[j];
  48.                 j++;
  49.                 k++;
  50.         }
  51. }
  52.  
  53. void mergeSort(int arr[], int l, int r)
  54. {
  55.         if (l < r)
  56.         {
  57.                 int m = l+(r-l)/2;
  58.  
  59.                 mergeSort(arr, l, m);
  60.                 mergeSort(arr, m+1, r);
  61.  
  62.                 merge(arr, l, m, r);
  63.         }
  64. }
  65. bool check(double x){
  66.         int np=0;//number of person
  67.         for(int i=1;i<=N;i++){
  68.                 np+= int (pi*r[i]*r[i]/x);
  69.         }
  70.         if(np >= F+1) return true;
  71.         else return false;
  72. }
  73. int main(){
  74.         ios::sync_with_stdio(0);
  75.         cin.tie(0);
  76.         int n;
  77.         cin>>n;
  78.         double upper=MAX,lower=tiny;
  79.         double x;
  80.         while(n--){
  81.                 cin>>N>>F;
  82.                 for(int i=1;i<=N;i++) cin>>r[i];
  83.                 mergeSort(r,1,N);
  84.                 while(upper - lower > tiny){
  85.                         x=double((upper+lower)/2);
  86.                         if(check(x)) lower=x;
  87.                         else upper=x;
  88.                 }
  89.                 cout<<setprecision(7)<<fixed<<x<<endl;
  90.         }
  91. }

Replies to Untitled rss

Title Name Language When
Re: Untitled Innocent Porcupine text 4 Years ago.