PGSStas

2019.03.19_B

Mar 19th, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define F first
  4. #define S second
  5. #define ll long long
  6. #define ull unsigned long long
  7. #define ld long double
  8. #define SELO ""
  9. #define openfiles ifstream cin("input"  SELO  ".txt"); ofstream cout("output"  SELO  ".txt");
  10. #define faster ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
  11. #define all(x) x.begin(), x.end()
  12.  
  13. using namespace std;
  14.  
  15. int main()
  16. {
  17.     openfiles
  18.     int n;
  19.     cin >> n;
  20.     vector <ld> res_L(n), res_R(n), sum_L(n), sum_R(n);
  21.     vector <pair <ld, ld> > y(n);
  22.     for(int i = 0; i < n; i++)
  23.         cin >> y[i].F >> y[i].S;
  24.     sort(all(y));
  25.     ll sum = 0, kol = 0;
  26.     for(int i = 0; i < n; i++)
  27.     {
  28.         sum += y[i].S;
  29.         kol += y[i].S * y[i].S;
  30.         res_L[i] = (1.0 * sum) / (i + 1);
  31.         sum_L[i] = (i + 1) * res_L[i] * res_L[i] - 2 * sum * res_L[i] + kol;
  32.     }
  33.     sum = 0, kol = 0;
  34.     for(int i = 0; i < n; i++)
  35.     {
  36.         sum += y[n - 1 - i].S;
  37.         kol += y[n - 1 - i].S * y[n - 1 - i].S;
  38.         res_R[n - 1 - i] = 1.0 * sum / (1.0 * (i + 1));
  39.         sum_R[n - 1 - i] = (i + 1) * res_R[n - 1 - i] * res_R[n - 1 - i] - 2 * sum * res_R[n - 1 - i] + kol;
  40.     }
  41.     ld ans = 1000000000000000000.0, l = -1, r = -1, c = 0;
  42.     if(ans > sum_R[0])
  43.     {
  44.         ans = sum_R[0];
  45.         l = 1.0;
  46.         r = res_R[0];
  47.         c = y[0].F - 0.5;
  48.     }
  49.     if(ans > sum_L[n - 1])
  50.     {
  51.         ans = sum_L[n - 1];
  52.         l = res_L[n - 1];
  53.         r = 1.0;
  54.         c = y[n - 1].F + 0.5;
  55.     }
  56.     for(int i = 0; i < n - 1; i++)
  57.     {
  58.         if(abs(y[i + 1].F - y[i].F) <= 0.1)
  59.             continue;
  60.         if(ans > sum_L[i] + sum_R[i + 1])
  61.         {
  62.             ans = sum_L[i] + sum_R[i + 1];
  63.             l = res_L[i];
  64.             r = res_R[i + 1];
  65.             c = y[i + 1].F - 0.5;
  66.         }
  67.     }
  68.     cout << fixed << setprecision(20) << l << " " << r << " " << c;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment