Advertisement
Guest User

Untitled

a guest
Jul 23rd, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.50 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #pragma comment(linker, "/STACK:32000000")
  4. #pragma GCC optimize("O3")
  5.  
  6. #include <stdio.h>
  7. #include <string.h>
  8. #include <memory.h>
  9. #include <stdlib.h>
  10. #include <iostream>
  11. #include <time.h>
  12. #include <algorithm>
  13. #include <math.h>
  14. #include <vector>
  15. #include <set>
  16. #include <queue>
  17. #include <stack>
  18. #include <bitset>
  19. #include <string>
  20. #include <cstring>
  21. #include <cassert>
  22. #include <fstream>
  23. #include <map>
  24. #include <unordered_map>
  25. #include <deque>
  26.  
  27. using namespace std;
  28.  
  29. #define inf 1000000007
  30. #define eps 1e-7
  31. #define mp(a, b) make_pair(a, b)
  32. #define llinf 2000000000000000008LL
  33.  
  34. typedef long long ll;
  35. typedef unsigned u;
  36. typedef long double ld;
  37. typedef unsigned char uc;
  38. typedef unsigned long long ull;
  39.  
  40. int n;
  41. int x[100005];
  42. int v[100005];
  43.  
  44. long double f(long double t) {
  45. long double mn = llinf, mx = -llinf;
  46. for (int i = 0; i < n; i++) {
  47. long double now = 1.0 * x[i] + 1.0 * v[i] * t;
  48. mn = min(mn, now);
  49. mx = max(mx, now);
  50. }
  51. return mx - mn;
  52. }
  53.  
  54. int main() {
  55. ios_base::sync_with_stdio(0);
  56. cin.tie(0);
  57. cout.tie(0);
  58. cin.sync_with_stdio(0);
  59. cout.sync_with_stdio(0);
  60. cout.precision(8);
  61. srand(time(0));
  62.  
  63. cin >> n;
  64. for (int i = 0; i < n; i++) {
  65. cin >> x[i] >> v[i];
  66. }
  67. long double l = 0, r = llinf;
  68. for (int i = 0; i < 400; i++) {
  69. long double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
  70. if (f(m1) > f(m2)) {
  71. l = m1;
  72. }
  73. else {
  74. r = m2;
  75. }
  76. }
  77.  
  78. cout << fixed << r << " " << f(r);
  79. return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement