Advertisement
Guest User

Untitled

a guest
Feb 13th, 2016
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.37 KB | None | 0 0
  1. #define _CRT_DISABLE_PERFCRIT_LOCKS
  2. #pragma comment(linker, "/STACK:16777216")
  3.  
  4. #include <cctype>
  5. #include <vector>
  6. #include <map>
  7. #include <set>
  8. #include <complex>
  9. #include <ctime>
  10. #include <iostream>
  11. #include <fstream>
  12. #include <time.h>
  13. #include <cmath>
  14. #include <stack>
  15. #include <stdio.h>
  16. #include <list>
  17. #include <algorithm>
  18. #include <unordered_map>
  19. #include <queue>
  20. #include <unordered_set>
  21. #include <random>
  22.  
  23.  
  24. const long double PI(acos(-1.0));
  25.  
  26. #define pb push_back
  27. #define mp(a,b) make_pair(a,b)
  28. #define all(x) x.begin(), x.end()
  29. #define sqr(x) ((x)*(x))
  30. #define F first
  31. #define S second
  32. #define eps 1e-14
  33. #define inf (int)(1e9+7)
  34. #define infll (ll)(1e18+3)
  35. #define sz(x) ((int)x.size())
  36. #define bits(x) __builtin_popcount(x)
  37. #define bitsl(x) __builtin_popcountll(x)
  38.  
  39.  
  40. using namespace std;
  41. typedef unsigned long long ull;
  42. typedef long long ll;
  43. typedef long double ld;
  44. typedef vector < ll > vll;
  45. typedef vector<int> vi;
  46. typedef pair < ll, ll > pll;
  47. typedef pair < int, int > pii;
  48. typedef vector<vi> vii;
  49. typedef int huint;
  50.  
  51. const int N = 5050;
  52. ll sums[N];
  53. ll prs[N<<1];
  54. ll smtr[N<<1];
  55. ll allprs = 0;
  56.  
  57. int main() {
  58. #ifndef LOCAL_COMP
  59. // freopen("evacuate.in", "r", stdin);
  60. // freopen("evacuate.out", "w", stdout);
  61. #else
  62. freopen("/Users/nikita/Desktop/acm/acm/input.txt", "r", stdin);
  63. //freopen("/Users/nikita/Desktop/acm/acm/output.txt", "w", stdout);
  64. #endif
  65. cout.precision(10);
  66.  
  67.  
  68. int n; cin >> n;
  69. allprs = n*(n-1)/2;
  70. vi a(n);
  71. for (int i = 0; i<n; ++i)
  72. cin >> a[i];
  73. for (int i = 0; i<n; ++i)
  74. for (int j = i+1; j<n; ++j)
  75. sums[abs(a[i]-a[j])]++;
  76.  
  77. for (int i = 0; i<N-20; ++i) {
  78. for (int j = i; j<N-20; ++j) {
  79. prs[i+j] += sums[i] * sums[j];
  80. }
  81. }
  82. for (int i = (N<<1)-20; i>=0; --i)
  83. smtr[i] = sums[i] + smtr[i+1];
  84.  
  85.  
  86. ld ans = 0;
  87. for (int i = 1; i<N-20; ++i) {
  88. if (!sums[i] || !smtr[i+1] || !prs[i]) continue;
  89. ld verchspr = (prs[i] + .0) / (allprs + .0);
  90. verchspr /= (allprs + .0);
  91. verchspr *= (smtr[i+1] + .0);
  92. verchspr /= (allprs + .0);
  93. ans += verchspr;
  94. }
  95. cout << fixed << ans / allprs;
  96.  
  97.  
  98.  
  99. #ifdef LOCAL_COMP
  100. cerr << "\n == TIME : " << clock() / ld(CLOCKS_PER_SEC) << " == " << endl;
  101. #endif
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement