fork download
copy 
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. vector <double> x, y;
  6. vector <double> si, co;
  7.  
  8. double d;
  9.  
  10. const int N = 2500;
  11. const double h = 2 * acos(-1.0) / N;
  12.  
  13. double getF(int j) {
  14.     double minX = 1e9, maxX = -1e9;
  15.  
  16.     for (int i = 0; i < (int)x.size(); ++i) {
  17.         double xx = x[i] * co[j] + y[i] * si[j];
  18.         minX = min(minX, xx);
  19.         maxX = max(maxX, xx);
  20.     }
  21.     return min(d, maxX - minX);
  22. }
  23.  
  24.  
  25.  
  26. double get() {
  27.     double sum = 0;
  28.     for (int i = 0; i <= N; ++i) {
  29.         sum += getF(i) * ((i==0 || i==N) ? 1 : ((i&1)==0) ? 2 : 4);
  30.     }
  31.     sum /= 3 * N;
  32.     sum /= d;
  33.     return sum;
  34. }
  35.  
  36.  
  37. int main() {
  38. #ifdef LOCAL
  39.     freopen("input.txt", "r", stdin);
  40.     //freopen("output.txt", "w", stdout);
  41. #else
  42.  
  43. #endif
  44.  
  45.     co.resize(N + 1);
  46.     si.resize(N + 1);
  47.  
  48.     for (int i = 0; i <= N; ++i) {
  49.         co[i] = cos(i * h);
  50.         si[i] = sin(i * h);
  51.     }
  52.  
  53.     int t;
  54.     cin >> t;
  55.  
  56.     cout << setprecision(10) << fixed;
  57.  
  58.     while (t--) {
  59.         int n;
  60.         scanf("%d%lf", &n, &d);
  61.  
  62.         x.resize(n);
  63.         y.resize(n);
  64.  
  65.         for (int i = 0; i < n; ++i) {
  66.             scanf("%lf%lf", &x[i], &y[i]);
  67.         }
  68.         cout << get() << "\n";
  69.     }
  70.  
  71.     return 0;
  72. };
Runtime error #stdin #stdout #stderr 0s 4272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/ikavXq
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!