SHARE
TWEET

Untitled

Stepavly Jul 17th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <math.h>
  4. #include <algorithm>
  5. #include <set>
  6. #include <iostream>
  7. #include <vector>
  8. #include <queue>
  9. #include <map>
  10. #include <string>
  11. #include <time.h>
  12. #include <cassert>
  13. #include <functional>
  14. #include <memory.h>
  15. #include <stack>
  16. #include <bitset>
  17. #include <unordered_map>
  18. #include <unordered_set>
  19. #include <random>
  20. #include <chrono>
  21. #include <fstream>
  22. #include <climits>
  23. using namespace std;
  24.  
  25. typedef unsigned long long ull;
  26. typedef long long ll;
  27. typedef unsigned u;
  28. typedef long double ld;
  29. typedef vector<vector<int>> vvi;
  30. typedef unsigned char uc;
  31. typedef unsigned short us;
  32.  
  33. #define mp(a, b) make_pair(a, b)
  34. #define pb(a) push_back(a)
  35. #define INF 1000000000
  36. #define LLINF 1000000000000000000LL
  37. #define EPS 1e-14l
  38. #define pii pair<int, int>
  39. #define puu pair<u, u>
  40.  
  41. const char DEBUG = 0;
  42.  
  43. mt19937 gen((u)chrono::high_resolution_clock::now().time_since_epoch().count());
  44.  
  45. #pragma comment(linker, "/STACK:16777216")
  46.  
  47. int pos[100000];
  48. int vel[100000];
  49. int n;
  50.  
  51. ld get_dist(ld t)
  52. {
  53.     ld min_x = -1;
  54.     ld max_x = 0;
  55.  
  56.     for (int i = 0; i < n; i++)
  57.     {
  58.         ld x = pos[i] + vel[i] * t;
  59.  
  60.         if (min_x < 0 || min_x > x)
  61.             min_x = x;
  62.  
  63.         max_x = max(max_x, x);
  64.     }
  65.  
  66.     return max_x - min_x;
  67. }
  68.  
  69. ld ternary(ld l, ld r)
  70. {
  71.     while (r - l > 1e-13l)
  72.     {
  73.         ld m1 = l + (r - l) / 3;
  74.         ld m2 = r - (r - l) / 3;
  75.  
  76.         ld d1 = get_dist(m1);
  77.         ld d2 = get_dist(m2);
  78.  
  79.         if (d1 < d2)
  80.             r = m2;
  81.         else
  82.             l = m1;
  83.     }
  84.  
  85.     return (l + r) / 2;
  86. }
  87.  
  88. int main()
  89. {
  90.     ios_base::sync_with_stdio(0);
  91.     cin.tie(0);
  92.  
  93.     cin >> n;
  94.  
  95.     for (int i = 0; i < n; i++)
  96.         cin >> pos[i] >> vel[i];
  97.  
  98.     ld best_t = 0;
  99.     int r = 10000000;
  100.     ld prev_dist = get_dist(ternary(0, 1));
  101.  
  102.     for (int i = 1; i <= 10000000 / 2; i *= 2)
  103.     {
  104.         ld cur_dist = get_dist(ternary(i, 2 * i));
  105.  
  106.         if (prev_dist < cur_dist + 1e-6)
  107.         {
  108.             r = i;
  109.             break;
  110.         }
  111.  
  112.         prev_dist = cur_dist;
  113.     }
  114.  
  115.     best_t = ternary(r / 2, r);
  116.     cout.precision(8);
  117.     cout << fixed << best_t << " " << get_dist(best_t);
  118.  
  119.     return 0;
  120. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top