Advertisement
Guest User

Untitled

a guest
Dec 18th, 2017
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7.  
  8. #define f first
  9. #define sec second
  10. #define mk make_pair
  11. #define pb push_back
  12. //#define int ll
  13. #define all(x) x.begin(), x.end()
  14.  
  15. const int INF = 1e9 + 10;
  16. const int N = 2e5 + 10;
  17.  
  18. struct st {
  19. ld f, t;
  20. int sec;
  21. };
  22.  
  23. bool cmp(st a, st b) {
  24. return a.t < b.t || (a.t == b.t && a.sec > b.sec);
  25. }
  26.  
  27. inline vector<st> unique(vector<st> &arr) {
  28. vector<st> res;
  29. res.pb(arr[0]);
  30. for (int i = 1; i < arr.size(); i++) {
  31. if (arr[i].f + arr[i].sec != res.back().f + res.back().sec) {
  32. res.pb(arr[i]);
  33. }
  34. }
  35. return res;
  36. }
  37.  
  38. inline ld solve(vector<st> arr) {
  39. ld ans = -INF;
  40. sort(all(arr), cmp);
  41. arr = unique(arr);
  42. int n = arr.size();
  43. vector<ld> suf(n);
  44. suf[n - 1] = arr[n - 1].f - arr[n - 1].sec;
  45. for (int i = n - 2; i >= 0; i--) {
  46. suf[i] = min(suf[i + 1], arr[i].f - arr[i].sec);
  47. }
  48. for (int i = 0; i + 1 < arr.size(); i++) {
  49. ans = max(ans, suf[i + 1] - (arr[i].f + arr[i].sec));
  50. }
  51. if (ans < 0) {
  52. cout << -1;
  53. exit(0);
  54. }
  55. else {
  56. return ans;
  57. }
  58. }
  59.  
  60. signed main() {
  61. #ifdef HOME
  62. freopen("input.txt", "r", stdin);
  63. //freopen("output.txt", "w", stdout);
  64. #endif
  65. cin.tie(0);
  66. cout.tie(0);
  67. ios_base::sync_with_stdio(0);
  68. ld x1, x2, y1, y2;
  69. cin >> x1 >> y1 >> x2 >> y2;
  70. if (x1 == x2) {
  71. int n;
  72. cin >> n;
  73. vector<st> arr(n);
  74. for (int i = 0; i < n; i++) {
  75. cin >> arr[i].f >> arr[i].sec >> arr[i].sec;
  76. arr[i].t = arr[i].f + arr[i].sec;
  77. }
  78. cout << fixed << setprecision(10) << solve(arr);
  79. }
  80. else if (y1 == y2) {
  81. int n;
  82. cin >> n;
  83. vector<st> arr(n);
  84. for (int i = 0; i < n; i++) {
  85. cin >> arr[i].f >> arr[i].f >> arr[i].sec;
  86. arr[i].t = arr[i].f + arr[i].sec;
  87. }
  88. cout << fixed << setprecision(10) << solve(arr);
  89. }
  90. else {
  91. ld k = (y2 - y1) / (x2 - x1);
  92. ld a = 1, b = abs(-1.0 / k), c = sqrt(a * a + b * b), d = abs(a * b / c);
  93. int n;
  94. cin >> n;
  95. vector<st> arr(n);
  96. for (int i = 0; i < n; i++) {
  97. ld x, y, r;
  98. cin >> x >> y >> r;
  99. arr[i].f = (y - k * x) * d;
  100. arr[i].sec = r;
  101. arr[i].t = arr[i].f + arr[i].sec;
  102. }
  103. cout << fixed << setprecision(10) << solve(arr);
  104. }
  105. return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement