Advertisement
Tevronis

519

Dec 9th, 2016
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.35 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <cstdlib>
  5. #include <deque>
  6. #include <cmath>
  7. #include <iomanip>
  8. #include <algorithm>
  9.  
  10. using namespace std;
  11. typedef pair<int, int> pii;
  12. typedef pair<double, double> pdd;
  13. typedef long long li;
  14. typedef long double ld;
  15. #define forn(i,n) for(int (i) = 0; (i) < n; ++(i))
  16. #define EPS 1e-18
  17.  
  18. bool zero(double x) {
  19. return abs(x) < EPS;
  20. }
  21.  
  22. const double INF = 1e19;
  23.  
  24. struct tp {
  25. int x, v;
  26. };
  27.  
  28. bool operator < (const tp &a, const tp &b) {
  29. return a.x < b.x;
  30. }
  31.  
  32. tp p[500500];
  33. int n;
  34.  
  35. inline bool equal(double a, double b) {
  36. return b - a > -EPS;
  37. }
  38.  
  39. bool f(double mid) {
  40. bool result = false;
  41. double maxx = -INF;
  42. for (int i = 0; i < n; i++) {
  43. double cur = (double)p[i].v * mid + p[i].x;
  44. if (p[i].v < 0) {
  45. if (equal(cur, maxx)) {
  46. result = true;
  47. break;
  48. }
  49. continue;
  50. }
  51. maxx = max(maxx, cur);
  52. }
  53. return result;
  54. }
  55.  
  56. int main() {
  57. #ifdef _DEBUG
  58. freopen("input.txt", "r", stdin);
  59. freopen("output.txt", "w", stdout);
  60. #endif
  61. scanf("%d", &n);
  62. for (int i = 0; i < n; ++i)
  63. scanf("%d %d", &p[i].x, &p[i].v);
  64.  
  65. sort(p, p + n);
  66. double ans = -1;
  67. double l = 0, r = 2e9;
  68. for (int i = 0; i < 100; ++i) {
  69. double mid = (l + r) / 2;
  70.  
  71. if (f(mid))
  72. ans = mid, r = mid;
  73. else
  74. l = mid;
  75. }
  76. printf("%.18lf\n", ans);
  77.  
  78. return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement