Advertisement
OIQ

task628

OIQ
Nov 5th, 2019
176
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <math.h>
  5.  
  6. using namespace std;
  7.  
  8. long double len(vector <vector <int>> &a, int x) {
  9.  
  10.     long double sum = 0;
  11.  
  12.     for (int i = 0; i < a.size(); i++)
  13.         sum += sqrt(   1LL * (a[i][0] - x) * (a[i][0] - x) +  1LL * (a[i][1]) * (a[i][1])    );
  14.  
  15.     return sum;
  16.  
  17. }
  18.  
  19. int main() {
  20.  
  21.     int n;
  22.     cin >> n;
  23.  
  24.  
  25.     vector <vector <int>> a(n-2, vector <int>(2));
  26.  
  27.     int x1, y1, x2, y2;
  28.     cin >> x1 >> y1 >> x2 >> y2;
  29.  
  30.     if (n == 2) {
  31.         cout << x1;
  32.         return 0;
  33.     }
  34.  
  35.     for (int i = 0; i < n - 2; i++) {
  36.         cin >> a[i][0];
  37.         cin >> a[i][1];
  38.     }
  39.  
  40.     int l = min(x1, x2);
  41.     int r = max(x1, x2);
  42.  
  43.  
  44.     while (r - l > 3) {
  45.         int m1 = l + (r - l) / 3;
  46.         int m2 = r - (r - l) / 3;
  47.  
  48.         if (len(a, m1) > len(a, m2))
  49.             l = m1;
  50.         else if (len(a, m1) < len(a, m2))
  51.             r = m2;
  52.         else {
  53.             l = m1;
  54.             r = m2;
  55.         }
  56.     }
  57.  
  58.  
  59.     vector <long double> b(5);
  60.  
  61.     b[0] = len(a, x1);
  62.     b[1] = len(a, l);
  63.     b[2] = len(a, l + 1);
  64.     b[3] = len(a, r);
  65.     b[4] = len(a, x2);
  66.  
  67.     long double min = b[0];
  68.  
  69.     for (int i = 1; i < b.size(); i++)
  70.         if (min > b[i])
  71.             min = b[i];
  72.     cout << min;
  73.     return 0;
  74. }
Advertisement
RAW Paste Data Copied
Advertisement