Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- #define vi vector <int>
- #define all(v) v.begin(), v.end()
- #define pii pair <int, int>
- #define mp(a, b) make_pair(a, b)
- #define forn(i, from, n) for (int i = (int)(from); i < (int)(n); ++i)
- const int INF = 1e9 + 9;
- void upd(int &a, int b){
- if (a < b) a = b;
- }
- int get1(int t1, int l2, int r2, int s1, int d1, int s2, int d2){
- // if (t1 + d1 + d2 > r2) return INF + abs(t1 - s1) + abs(t1 + d1 - s2);
- return abs(t1 - s1) + abs(t1 + d1 - s2);
- }
- int get2(int t1, int l2, int r2, int s1, int d1, int s2, int d2){
- // if (t1 - d2 < l2 || t1 > r2) return INF + abs(s2 - (t1 - d2)) + abs(t1 + d1 - s1);
- return abs(s2 - (t1 - d2)) + abs(t1 - s1);
- }
- bool check(int t1, int d1, int l1, int r1, int t2, int d2, int l2, int r2){
- if (t1 >= l1 && t1 + d1 <= r1 && t2 >= l2 && t2 + d2 <= r2) return 1;
- return 0;
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- #ifdef LOCAL
- freopen("in", "r", stdin);
- freopen("out", "w", stdout);
- #endif
- int t;
- cin >> t;
- while (t--){
- int l1, r1, l2, r2, s1, d1, s2, d2;
- cin >> l1 >> r1 >> l2 >> r2 >> s1 >> d1 >> s2 >> d2;
- if (s1 + d1 <= s2){
- cout << s1 << ' ' << s2 << '\n';
- continue;
- }
- if (s2 + d2 <= s1){
- cout << s1 << ' ' << s2 << '\n';
- continue;
- }
- int l = max(l1, l2 - d1), r = min(r1 - d1 + 1, r2 - d1 - d2 + 1);
- while (r - l > 2){
- int m1 = l + (r - l) / 3;
- int m2 = r - (r - l) / 3;
- if (get1(m1, l2, r2, s1, d1, s2, d2) < get1(m2, l2, r2, s1, d1, s2, d2))
- r = m2;
- else
- l = m1;
- }
- int ans = INF;
- int type = 1, al;
- if (check(l, d1, l1, r1, l + d1, d2, l2, r2) && get1(l, l2, r2, s1, d1, s2, d2) < ans){
- ans = get1(l, l2, r2, s1, d1, s2, d2);
- al = l;
- }
- 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){
- ans = get1(l + 1, l2, r2, s1, d1, s2, d2);
- al = l + 1;
- }
- if (check(r, d1, l1, r1, r + d1, d2, l2, r2) && r + d1 <= r1 && get1(r, l2, r2, s1, d1, s2, d2) < ans){
- ans = get1(r, l2, r2, s1, d1, s2, d2);
- al = r;
- }
- l = max(l1, l2 + d2), r = min(r1 - d1 + 1, r2 + d1 + 1);
- while (r - l > 2){
- int m1 = l + (r - l) / 3;
- int m2 = r - (r - l) / 3;
- if (get2(m1, l2, r2, s1, d1, s2, d2) < get2(m2, l2, r2, s1, d1, s2, d2))
- r = m2;
- else
- l = m1;
- }
- if (check(l, d1, l1, r1, l - d2, d2, l2, r2) && get2(l, l2, r2, s1, d1, s2, d2) < ans){
- ans = get2(l, l2, r2, s1, d1, s2, d2);
- type = 2;
- al = l;
- }
- 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){
- ans = get2(l + 1, l2, r2, s1, d1, s2, d2);
- type = 2;
- al = l + 1;
- }
- if (check(r, d1, l1, r1, r - d2, d2, l2, r2) && r + d1 <= r1 && get2(r, l2, r2, s1, d1, s2, d2) < ans){
- ans = get2(r, l2, r2, s1, d1, s2, d2);
- type = 2;
- al = r;
- }
- if (ans >= INF)
- cout << "-1 -1\n";
- else if (type == 1)
- cout << al << ' ' << al + d1 << '\n';
- else cout << al << ' ' << al - d2 << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement