Advertisement
Guest User

Untitled

a guest
Feb 20th, 2020
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. bool comp(long long a, long long b) {
  7.     return a < b;
  8. }
  9.  
  10. void quick_sort(long long *vector, int first, int last) {
  11.     long long mid;
  12.     int f = first, l = last;
  13.     mid = vector[(f + l) / 2];
  14.     do {
  15.         while (comp(vector[f], mid)) f++;
  16.         while (comp(mid, vector[l])) l--;
  17.         if (f <= l)
  18.         {
  19.             swap(vector[f], vector[l]);
  20.             f++;
  21.             l--;
  22.         }
  23.     } while (f < l);
  24.     if (first < l) quick_sort(vector, first, l);
  25.     if (f < last) quick_sort(vector, f, last);
  26. }
  27.  
  28. int main() {
  29.     long long n;
  30.     cin >> n;
  31.     long long x_s[n];
  32.     long long y_s[n];
  33.     long long sum = 0;
  34.     for (long long i = 0; i < n; ++i) {
  35.         cin >> x_s[i] >> y_s[i];
  36.     }
  37.  
  38.     quick_sort(x_s,0,n-1);
  39.     quick_sort(y_s,0,n-1);
  40.  
  41. //    sort(x_s, x_s + n, comp);
  42. //    sort(y_s, y_s + n, comp);
  43.  
  44.     for (long long i = 0; i < n - 1; ++i) {
  45.         sum += (x_s[i + 1] - x_s[i]) * (i + 1) * (n - i - 1);
  46.         sum += (y_s[i + 1] - y_s[i]) * (i + 1) * (n - i - 1);
  47.     }
  48.  
  49.     sum = 2 * sum / (n * (n - 1));
  50.     cout << sum;
  51.     return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement