Advertisement
Guest User

Untitled

a guest
Dec 14th, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.61 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define vi vector <int>
  7. #define all(v) v.begin(), v.end()
  8. #define pii pair <int, int>
  9. #define mp(a, b) make_pair(a, b)
  10. #define forn(i, from, n) for (int i = (int)(from); i < (int)(n); ++i)
  11.  
  12. const int INF = 1e9 + 9;
  13.  
  14. void upd(int &a, int b){
  15. if (a < b) a = b;
  16. }
  17.  
  18. int get1(int t1, int l2, int r2, int s1, int d1, int s2, int d2){
  19. // if (t1 + d1 + d2 > r2) return INF + abs(t1 - s1) + abs(t1 + d1 - s2);
  20. return abs(t1 - s1) + abs(t1 + d1 - s2);
  21. }
  22.  
  23. int get2(int t1, int l2, int r2, int s1, int d1, int s2, int d2){
  24. // if (t1 - d2 < l2 || t1 > r2) return INF + abs(s2 - (t1 - d2)) + abs(t1 + d1 - s1);
  25. return abs(s2 - (t1 - d2)) + abs(t1 - s1);
  26. }
  27.  
  28. bool check(int t1, int d1, int l1, int r1, int t2, int d2, int l2, int r2){
  29. if (t1 >= l1 && t1 + d1 <= r1 && t2 >= l2 && t2 + d2 <= r2) return 1;
  30. return 0;
  31. }
  32.  
  33. signed main() {
  34. ios_base::sync_with_stdio(false);
  35. cin.tie(0); cout.tie(0);
  36.  
  37. #ifdef LOCAL
  38. freopen("in", "r", stdin);
  39. freopen("out", "w", stdout);
  40. #endif
  41.  
  42. int t;
  43. cin >> t;
  44. while (t--){
  45. int l1, r1, l2, r2, s1, d1, s2, d2;
  46. cin >> l1 >> r1 >> l2 >> r2 >> s1 >> d1 >> s2 >> d2;
  47. if (s1 + d1 <= s2){
  48. cout << s1 << ' ' << s2 << '\n';
  49. continue;
  50. }
  51. if (s2 + d2 <= s1){
  52. cout << s1 << ' ' << s2 << '\n';
  53. continue;
  54. }
  55. int l = max(l1, l2 - d1), r = min(r1 - d1 + 1, r2 - d1 - d2 + 1);
  56. while (r - l > 2){
  57. int m1 = l + (r - l) / 3;
  58. int m2 = r - (r - l) / 3;
  59. if (get1(m1, l2, r2, s1, d1, s2, d2) < get1(m2, l2, r2, s1, d1, s2, d2))
  60. r = m2;
  61. else
  62. l = m1;
  63. }
  64. int ans = INF;
  65. int type = 1, al;
  66. if (check(l, d1, l1, r1, l + d1, d2, l2, r2) && get1(l, l2, r2, s1, d1, s2, d2) < ans){
  67. ans = get1(l, l2, r2, s1, d1, s2, d2);
  68. al = l;
  69. }
  70. if (check(l + 1, d1, l1, r1, l + 1 + d1, d2, l2, r2) && l + 1 + d1 <= r1 && get1(l + 1, l2, r2, s1, d1, s2, d2) < ans){
  71. ans = get1(l + 1, l2, r2, s1, d1, s2, d2);
  72. al = l + 1;
  73. }
  74. if (check(r, d1, l1, r1, r + d1, d2, l2, r2) && r + d1 <= r1 && get1(r, l2, r2, s1, d1, s2, d2) < ans){
  75. ans = get1(r, l2, r2, s1, d1, s2, d2);
  76. al = r;
  77. }
  78. l = max(l1, l2 + d2), r = min(r1 - d1 + 1, r2 + d1 + 1);
  79. while (r - l > 2){
  80. int m1 = l + (r - l) / 3;
  81. int m2 = r - (r - l) / 3;
  82. if (get2(m1, l2, r2, s1, d1, s2, d2) < get2(m2, l2, r2, s1, d1, s2, d2))
  83. r = m2;
  84. else
  85. l = m1;
  86. }
  87. if (check(l, d1, l1, r1, l - d2, d2, l2, r2) && get2(l, l2, r2, s1, d1, s2, d2) < ans){
  88. ans = get2(l, l2, r2, s1, d1, s2, d2);
  89. type = 2;
  90. al = l;
  91. }
  92. if (check(l + 1, d1, l1, r1, l + 1 - d2, d2, l2, r2) && l + 1 + d1 <= r1 && get2(l + 1, l2, r2, s1, d1, s2, d2) < ans){
  93. ans = get2(l + 1, l2, r2, s1, d1, s2, d2);
  94. type = 2;
  95. al = l + 1;
  96. }
  97. if (check(r, d1, l1, r1, r - d2, d2, l2, r2) && r + d1 <= r1 && get2(r, l2, r2, s1, d1, s2, d2) < ans){
  98. ans = get2(r, l2, r2, s1, d1, s2, d2);
  99. type = 2;
  100. al = r;
  101. }
  102. if (ans >= INF)
  103. cout << "-1 -1\n";
  104. else if (type == 1)
  105. cout << al << ' ' << al + d1 << '\n';
  106. else cout << al << ' ' << al - d2 << '\n';
  107. }
  108. return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement