Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Do not start with all pairs of pipes. That is , which is just CPU arson with extra steps. First build the convex hull of one set and classify the other set's points as inside/on it or outside it.
If one set has a point inside/on the other set's convex hull and another point outside it, the segment between those two points must hit the hull boundary. A hull boundary edge is already a valid segment from the other set.
After that easy case is gone, at least one direction has this form: every point of is outside . Then the task becomes: find two outside points whose segment intersects this convex polygon.
For an outside point , consider all directed lines separating from the polygon, with the polygon on the left. Their directions form one circular arc bounded by the two tangents from to the polygon.
Two outside points avoid the polygon iff their separation-direction arcs overlap with positive length. So an answer exists iff two of these arcs have disjoint interiors. Compute tangent arcs, sort endpoints by angle, turn arcs into intervals on a doubled circle, and find two non-overlapping intervals.
We need choose two points from the first set and two points from the second set so that the two segments intersect.
The first false assumption to kill: intersecting convex hulls are not enough. A tiny segment inside a square can avoid all four square edges and both diagonals. So the hull matters, but not in the lazy way.
Step 1: Classify Points Against The Other Hull
Let the sets be and .
Build and classify every point of :
Do the same with and swapped.
Suppose has one point inside/on and one point outside it. Then segment must intersect the boundary of . That boundary consists of hull edges, and every hull edge is a segment between two original points of .
So we scan the hull edges of , find one intersecting , and output it.
Same logic works after swapping the sets.
Step 2: The All-Outside Case
If the mixed inside/outside case does not happen, then for each direction all points are on one side of the classification: either all inside/on or all outside.
At least one useful orientation exists where every point of one set lies outside the other set's convex hull. So assume:
Now we need two points such that segment intersects polygon .
If it does, since both endpoints are outside, the segment hits the boundary of , hence some hull edge of . That gives the required second pipe.
Visibility Arcs
For a point outside a convex polygon , look at all directed lines that separate from , with on the left side of the directed line.
The possible directions form one circular arc .
Its endpoints are the two tangent directions from to :
Now take two outside points and .
If segment avoids , then the two convex sets and are disjoint, so there exists a separating line. That line's direction belongs to both and .
If and overlap with positive length, we can choose a separating direction and shift the line slightly, keeping both on one side and on the other. Then avoids .
So:
Touching counts. If the arcs only touch at an endpoint, the segment is tangent to the polygon, and that is still a valid intersection.
Finding Two Disjoint Arcs
For each outside point, compute the two tangent boundary directions. A direction is just an integer vector, so sort all arc endpoints by polar angle using half-plane plus cross product. No floating point needed.
Each circular arc becomes an interval on this cyclic order. If it wraps around, add to , where is the number of distinct endpoint directions. Duplicate every interval shifted by .
For an interval , another interval is disjoint from it if one copy lies fully inside the complementary interval:
Sort duplicated intervals by left endpoint and keep suffix minima of right endpoints. Then for each original interval, binary search the first interval starting at least and check whether some interval ending no later than exists.
If yes, those two points form an -segment that intersects .
Finally, scan the hull edges of to find the actual -segment it intersects.
Degenerate Hulls
A hull can be a segment if all points are collinear. Handle it directly:
Complexity
Convex hulls take:
Classifications, tangents, and arc sweep are all logarithmic or sorting-based, so the total per test case is:
Good enough for total points.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Pt {
ll x, y;
int id;
};
Pt operator-(const Pt& a, const Pt& b) { return {a.x - b.x, a.y - b.y, -1}; }
bool samePt(const Pt& a, const Pt& b) { return a.x == b.x && a.y == b.y; }
i128 cross(Pt a, Pt b) { return (i128)a.x * b.y - (i128)a.y * b.x; }
i128 cross(Pt a, Pt b, Pt c) { return cross(b - a, c - a); }
int sgn(i128 v) { return (v > 0) - (v < 0); }
bool byXY(const Pt& a, const Pt& b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
bool onSeg(Pt a, Pt b, Pt p) {
if (cross(a, b, p) != 0) return false;
return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}
bool segInter(Pt a, Pt b, Pt c, Pt d) {
i128 c1 = cross(a, b, c), c2 = cross(a, b, d);
i128 c3 = cross(c, d, a), c4 = cross(c, d, b);
if (sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0) return true;
return onSeg(a, b, c) || onSeg(a, b, d) || onSeg(c, d, a) || onSeg(c, d, b);
}
struct Hull {
vector<Pt> p, low, up;
};
Hull buildHull(vector<Pt> v) {
sort(v.begin(), v.end(), byXY);
vector<Pt> low, up;
for (Pt q : v) {
while (low.size() >= 2 && cross(low[low.size() - 2], low.back(), q) <= 0) low.pop_back();
low.push_back(q);
}
for (int i = (int)v.size() - 1; i >= 0; --i) {
Pt q = v[i];
while (up.size() >= 2 && cross(up[up.size() - 2], up.back(), q) <= 0) up.pop_back();
up.push_back(q);
}
vector<Pt> h = low;
for (int i = 1; i + 1 < (int)up.size(); ++i) h.push_back(up[i]);
if (h.size() == 1 && v.size() >= 2) h = {v.front(), v.back()};
return {h, low, up};
}
vector<pair<Pt, Pt>> hullEdges(const vector<Pt>& h) {
if ((int)h.size() == 2) return {{h[0], h[1]}};
vector<pair<Pt, Pt>> e;
for (int i = 0; i < (int)h.size(); ++i) e.push_back({h[i], h[(i + 1) % h.size()]});
return e;
}
bool inConvex(const vector<Pt>& p, Pt q) {
int n = (int)p.size();
if (n == 2) return onSeg(p[0], p[1], q);
if (cross(p[0], p[1], q) < 0) return false;
if (cross(p[0], p[n - 1], q) > 0) return false;
int l = 1, r = n - 1;
while (r - l > 1) {
int m = (l + r) / 2;
if (cross(p[0], p[m], q) >= 0) l = m;
else r = m;
}
return cross(p[l], p[(l + 1) % n], q) >= 0;
}
bool findHullHit(Pt a, Pt b, const vector<Pt>& h, Pt& c, Pt& d) {
for (auto [u, v] : hullEdges(h)) {
if (segInter(a, b, u, v)) {
c = u;
d = v;
return true;
}
}
return false;
}
struct Vec {
ll x, y;
};
bool sameDir(const Vec& a, const Vec& b) {
return (i128)a.x * b.y - (i128)a.y * b.x == 0 &&
(i128)a.x * b.x + (i128)a.y * b.y > 0;
}
int half(const Vec& a) {
return (a.y > 0 || (a.y == 0 && a.x > 0)) ? 0 : 1;
}
bool angleLess(const Vec& a, const Vec& b) {
int ha = half(a), hb = half(b);
if (ha != hb) return ha < hb;
i128 cr = (i128)a.x * b.y - (i128)a.y * b.x;
if (cr != 0) return cr > 0;
i128 da = (i128)a.x * a.x + (i128)a.y * a.y;
i128 db = (i128)b.x * b.x + (i128)b.y * b.y;
return da < db;
}
Vec vec(Pt a, Pt b) { return {b.x - a.x, b.y - a.y}; }
pair<int, int> tangents(const Hull& H, Pt q) {
const vector<Pt>& P = H.p;
int n = (int)P.size();
if (n == 2) return {0, 1};
const vector<Pt>& L = H.low;
const vector<Pt>& U = H.up;
int m = (int)L.size(), k = (int)U.size();
int lk = m;
if (samePt(L.back(), U.front())) --lk;
auto bs = [&](const vector<Pt>& A, int w) {
int l = 0, r = (int)A.size() - 1, res = 0;
i128 qx = (i128)q.x * w;
while (l <= r) {
int mid = (l + r) / 2;
if ((i128)A[mid].x * w >= qx) r = mid - 1;
else res = mid, l = mid + 1;
}
return res;
};
auto searchTang = [&](int l, int r, int w, int off) {
int res = l;
while (l <= r) {
int mid = (l + r) / 2;
int id = (mid + off) % n;
Pt cur = P[id], nxt = P[(id + 1) % n], prv = P[(id - 1 + n) % n];
i128 a = cross(cur - q, nxt - q) * w;
i128 b = cross(cur - q, prv - q) * w;
if (a >= 0 && b >= 0) return mid;
if (a >= 0) r = mid - 1, res = mid;
else l = mid + 1;
}
return res;
};
int t1 = bs(L, 1), t2 = bs(U, -1);
int left = -1, right = -1;
for (auto [cand, off] : vector<pair<int, int>>{{searchTang(0, t1, -1, 0), 0}, {searchTang(0, t2, -1, lk), lk}}) {
int id = (cand + off) % n;
if (cross(P[id] - q, P[(id - 1 + n) % n] - q) <= 0 &&
cross(P[id] - q, P[(id + 1) % n] - q) <= 0) {
left = id;
}
}
for (auto [cand, off] : vector<pair<int, int>>{{searchTang(t1, m - 1, 1, 0), 0}, {searchTang(t2, k - 1, 1, lk), lk}}) {
int id = (cand + off) % n;
if (cross(P[id] - q, P[(id - 1 + n) % n] - q) >= 0 &&
cross(P[id] - q, P[(id + 1) % n] - q) >= 0) {
right = id;
}
}
if (left == -1) left = 0;
if (right == -1) right = 0;
return {left, right};
}
struct Arc {
Vec s, e;
int pid;
};
bool findOutsidePair(const vector<Pt>& a, const Hull& obs, Pt& p, Pt& q) {
vector<Arc> arcs;
vector<Vec> dirs;
for (Pt x : a) {
Vec s, e;
if ((int)obs.p.size() == 2) {
Vec v0 = vec(x, obs.p[0]);
Vec v1 = vec(x, obs.p[1]);
if (angleLess(v1, v0)) swap(v0, v1);
if ((i128)v0.x * v1.y - (i128)v0.y * v1.x < 0) swap(v0, v1);
s = {-v1.x, -v1.y};
e = v0;
} else {
auto [le, ri] = tangents(obs, x);
s = vec(obs.p[le], x);
e = vec(x, obs.p[ri]);
}
arcs.push_back({s, e, x.id});
dirs.push_back(s);
dirs.push_back(e);
}
sort(dirs.begin(), dirs.end(), angleLess);
vector<Vec> uni;
for (Vec d : dirs) {
if (uni.empty() || !sameDir(uni.back(), d)) uni.push_back(d);
}
int M = (int)uni.size();
auto getPos = [&](Vec d) {
int l = 0, r = M - 1, ans = 0;
while (l <= r) {
int m = (l + r) / 2;
if (!angleLess(d, uni[m])) ans = m, l = m + 1;
else r = m - 1;
}
while (ans > 0 && sameDir(uni[ans - 1], d)) --ans;
return ans;
};
struct Itv {
int l, r, id;
};
vector<Itv> orig, all;
for (Arc a0 : arcs) {
int l = getPos(a0.s), r = getPos(a0.e);
if (angleLess(a0.e, a0.s) || sameDir(a0.s, a0.e)) r += M;
orig.push_back({l, r, a0.pid});
all.push_back({l, r, a0.pid});
all.push_back({l + M, r + M, a0.pid});
}
sort(all.begin(), all.end(), [](const Itv& a, const Itv& b) {
if (a.l != b.l) return a.l < b.l;
return a.r < b.r;
});
int N = (int)all.size();
vector<int> sufR(N + 1, INT_MAX), sufId(N + 1, -1), starts;
starts.reserve(N);
for (auto z : all) starts.push_back(z.l);
for (int i = N - 1; i >= 0; --i) {
if (all[i].r < sufR[i + 1]) {
sufR[i] = all[i].r;
sufId[i] = all[i].id;
} else {
sufR[i] = sufR[i + 1];
sufId[i] = sufId[i + 1];
}
}
unordered_map<int, Pt> byId;
byId.reserve(a.size() * 2 + 1);
for (Pt x : a) byId[x.id] = x;
for (auto cur : orig) {
int L = cur.r;
int R = cur.l + M;
int pos = lower_bound(starts.begin(), starts.end(), L) - starts.begin();
int end = upper_bound(starts.begin(), starts.end(), R) - starts.begin();
if (pos < end && sufR[pos] <= R && sufId[pos] != cur.id) {
p = byId[cur.id];
q = byId[sufId[pos]];
return true;
}
}
return false;
}
bool mixedCase(const vector<Pt>& a, const Hull& hb, bool aFirst, array<int, 4>& ans) {
int in = -1, out = -1;
for (int i = 0; i < (int)a.size(); ++i) {
if (inConvex(hb.p, a[i])) in = i;
else out = i;
}
if (in == -1 || out == -1) return false;
Pt u, v;
if (!findHullHit(a[in], a[out], hb.p, u, v)) return false;
if (aFirst) ans = {a[in].id, a[out].id, u.id, v.id};
else ans = {u.id, v.id, a[in].id, a[out].id};
return true;
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n;
vector<Pt> A(n);
for (int i = 0; i < n; ++i) cin >> A[i].x >> A[i].y, A[i].id = i + 1;
cin >> m;
vector<Pt> B(m);
for (int i = 0; i < m; ++i) cin >> B[i].x >> B[i].y, B[i].id = i + 1;
Hull HA = buildHull(A), HB = buildHull(B);
array<int, 4> ans{-1, -1, -1, -1};
if (mixedCase(A, HB, true, ans) || mixedCase(B, HA, false, ans)) {
cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << ' ' << ans[3] << '\n';
continue;
}
bool allAOut = true, allBOut = true;
for (Pt x : A) allAOut &= !inConvex(HB.p, x);
for (Pt x : B) allBOut &= !inConvex(HA.p, x);
Pt p, q, u, v;
if (allAOut && findOutsidePair(A, HB, p, q) && findHullHit(p, q, HB.p, u, v)) {
cout << p.id << ' ' << q.id << ' ' << u.id << ' ' << v.id << '\n';
} else if (allBOut && findOutsidePair(B, HA, p, q) && findHullHit(p, q, HA.p, u, v)) {
cout << u.id << ' ' << v.id << ' ' << p.id << ' ' << q.id << '\n';
} else {
cout << -1 << '\n';
}
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Pt {
ll x, y;
int id;
};
Pt operator-(const Pt& a, const Pt& b) { return {a.x - b.x, a.y - b.y, -1}; }
bool samePt(const Pt& a, const Pt& b) { return a.x == b.x && a.y == b.y; }
i128 cross(Pt a, Pt b) { return (i128)a.x * b.y - (i128)a.y * b.x; }
i128 cross(Pt a, Pt b, Pt c) { return cross(b - a, c - a); }
int sgn(i128 v) { return (v > 0) - (v < 0); }
bool byXY(const Pt& a, const Pt& b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
bool onSeg(Pt a, Pt b, Pt p) {
if (cross(a, b, p) != 0) return false;
return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}
bool segInter(Pt a, Pt b, Pt c, Pt d) {
i128 c1 = cross(a, b, c), c2 = cross(a, b, d);
i128 c3 = cross(c, d, a), c4 = cross(c, d, b);
if (sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0) return true;
return onSeg(a, b, c) || onSeg(a, b, d) || onSeg(c, d, a) || onSeg(c, d, b);
}
struct Hull {
vector<Pt> p, low, up;
};
Hull buildHull(vector<Pt> v) {
sort(v.begin(), v.end(), byXY);
vector<Pt> low, up;
for (Pt q : v) {
while (low.size() >= 2 && cross(low[low.size() - 2], low.back(), q) <= 0) low.pop_back();
low.push_back(q);
}
for (int i = (int)v.size() - 1; i >= 0; --i) {
Pt q = v[i];
while (up.size() >= 2 && cross(up[up.size() - 2], up.back(), q) <= 0) up.pop_back();
up.push_back(q);
}
vector<Pt> h = low;
for (int i = 1; i + 1 < (int)up.size(); ++i) h.push_back(up[i]);
if (h.size() == 1 && v.size() >= 2) h = {v.front(), v.back()};
return {h, low, up};
}
vector<pair<Pt, Pt>> hullEdges(const vector<Pt>& h) {
if ((int)h.size() == 2) return {{h[0], h[1]}};
vector<pair<Pt, Pt>> e;
for (int i = 0; i < (int)h.size(); ++i) e.push_back({h[i], h[(i + 1) % h.size()]});
return e;
}
bool inConvex(const vector<Pt>& p, Pt q) {
int n = (int)p.size();
if (n == 2) return onSeg(p[0], p[1], q);
if (cross(p[0], p[1], q) < 0) return false;
if (cross(p[0], p[n - 1], q) > 0) return false;
int l = 1, r = n - 1;
while (r - l > 1) {
int m = (l + r) / 2;
if (cross(p[0], p[m], q) >= 0) l = m;
else r = m;
}
return cross(p[l], p[(l + 1) % n], q) >= 0;
}
bool findHullHit(Pt a, Pt b, const vector<Pt>& h, Pt& c, Pt& d) {
for (auto [u, v] : hullEdges(h)) {
if (segInter(a, b, u, v)) {
c = u;
d = v;
return true;
}
}
return false;
}
struct Vec {
ll x, y;
};
bool sameDir(const Vec& a, const Vec& b) {
return (i128)a.x * b.y - (i128)a.y * b.x == 0 &&
(i128)a.x * b.x + (i128)a.y * b.y > 0;
}
int half(const Vec& a) {
return (a.y > 0 || (a.y == 0 && a.x > 0)) ? 0 : 1;
}
bool angleLess(const Vec& a, const Vec& b) {
int ha = half(a), hb = half(b);
if (ha != hb) return ha < hb;
i128 cr = (i128)a.x * b.y - (i128)a.y * b.x;
if (cr != 0) return cr > 0;
i128 da = (i128)a.x * a.x + (i128)a.y * a.y;
i128 db = (i128)b.x * b.x + (i128)b.y * b.y;
return da < db;
}
Vec vec(Pt a, Pt b) { return {b.x - a.x, b.y - a.y}; }
pair<int, int> tangents(const Hull& H, Pt q) {
const vector<Pt>& P = H.p;
int n = (int)P.size();
if (n == 2) return {0, 1};
const vector<Pt>& L = H.low;
const vector<Pt>& U = H.up;
int m = (int)L.size(), k = (int)U.size();
int lk = m;
if (samePt(L.back(), U.front())) --lk;
auto bs = [&](const vector<Pt>& A, int w) {
int l = 0, r = (int)A.size() - 1, res = 0;
i128 qx = (i128)q.x * w;
while (l <= r) {
int mid = (l + r) / 2;
if ((i128)A[mid].x * w >= qx) r = mid - 1;
else res = mid, l = mid + 1;
}
return res;
};
auto searchTang = [&](int l, int r, int w, int off) {
int res = l;
while (l <= r) {
int mid = (l + r) / 2;
int id = (mid + off) % n;
Pt cur = P[id], nxt = P[(id + 1) % n], prv = P[(id - 1 + n) % n];
i128 a = cross(cur - q, nxt - q) * w;
i128 b = cross(cur - q, prv - q) * w;
if (a >= 0 && b >= 0) return mid;
if (a >= 0) r = mid - 1, res = mid;
else l = mid + 1;
}
return res;
};
int t1 = bs(L, 1), t2 = bs(U, -1);
int left = -1, right = -1;
for (auto [cand, off] : vector<pair<int, int>>{{searchTang(0, t1, -1, 0), 0}, {searchTang(0, t2, -1, lk), lk}}) {
int id = (cand + off) % n;
if (cross(P[id] - q, P[(id - 1 + n) % n] - q) <= 0 &&
cross(P[id] - q, P[(id + 1) % n] - q) <= 0) {
left = id;
}
}
for (auto [cand, off] : vector<pair<int, int>>{{searchTang(t1, m - 1, 1, 0), 0}, {searchTang(t2, k - 1, 1, lk), lk}}) {
int id = (cand + off) % n;
if (cross(P[id] - q, P[(id - 1 + n) % n] - q) >= 0 &&
cross(P[id] - q, P[(id + 1) % n] - q) >= 0) {
right = id;
}
}
if (left == -1) left = 0;
if (right == -1) right = 0;
return {left, right};
}
struct Arc {
Vec s, e;
int pid;
};
bool findOutsidePair(const vector<Pt>& a, const Hull& obs, Pt& p, Pt& q) {
vector<Arc> arcs;
vector<Vec> dirs;
for (Pt x : a) {
Vec s, e;
if ((int)obs.p.size() == 2) {
Vec v0 = vec(x, obs.p[0]);
Vec v1 = vec(x, obs.p[1]);
if (angleLess(v1, v0)) swap(v0, v1);
if ((i128)v0.x * v1.y - (i128)v0.y * v1.x < 0) swap(v0, v1);
s = {-v1.x, -v1.y};
e = v0;
} else {
auto [le, ri] = tangents(obs, x);
s = vec(obs.p[le], x);
e = vec(x, obs.p[ri]);
}
arcs.push_back({s, e, x.id});
dirs.push_back(s);
dirs.push_back(e);
}
sort(dirs.begin(), dirs.end(), angleLess);
vector<Vec> uni;
for (Vec d : dirs) {
if (uni.empty() || !sameDir(uni.back(), d)) uni.push_back(d);
}
int M = (int)uni.size();
auto getPos = [&](Vec d) {
int l = 0, r = M - 1, ans = 0;
while (l <= r) {
int m = (l + r) / 2;
if (!angleLess(d, uni[m])) ans = m, l = m + 1;
else r = m - 1;
}
while (ans > 0 && sameDir(uni[ans - 1], d)) --ans;
return ans;
};
struct Itv {
int l, r, id;
};
vector<Itv> orig, all;
for (Arc a0 : arcs) {
int l = getPos(a0.s), r = getPos(a0.e);
if (angleLess(a0.e, a0.s) || sameDir(a0.s, a0.e)) r += M;
orig.push_back({l, r, a0.pid});
all.push_back({l, r, a0.pid});
all.push_back({l + M, r + M, a0.pid});
}
sort(all.begin(), all.end(), [](const Itv& a, const Itv& b) {
if (a.l != b.l) return a.l < b.l;
return a.r < b.r;
});
int N = (int)all.size();
vector<int> sufR(N + 1, INT_MAX), sufId(N + 1, -1), starts;
starts.reserve(N);
for (auto z : all) starts.push_back(z.l);
for (int i = N - 1; i >= 0; --i) {
if (all[i].r < sufR[i + 1]) {
sufR[i] = all[i].r;
sufId[i] = all[i].id;
} else {
sufR[i] = sufR[i + 1];
sufId[i] = sufId[i + 1];
}
}
unordered_map<int, Pt> byId;
byId.reserve(a.size() * 2 + 1);
for (Pt x : a) byId[x.id] = x;
for (auto cur : orig) {
int L = cur.r;
int R = cur.l + M;
int pos = lower_bound(starts.begin(), starts.end(), L) - starts.begin();
int end = upper_bound(starts.begin(), starts.end(), R) - starts.begin();
if (pos < end && sufR[pos] <= R && sufId[pos] != cur.id) {
p = byId[cur.id];
q = byId[sufId[pos]];
return true;
}
}
return false;
}
bool mixedCase(const vector<Pt>& a, const Hull& hb, bool aFirst, array<int, 4>& ans) {
int in = -1, out = -1;
for (int i = 0; i < (int)a.size(); ++i) {
if (inConvex(hb.p, a[i])) in = i;
else out = i;
}
if (in == -1 || out == -1) return false;
Pt u, v;
if (!findHullHit(a[in], a[out], hb.p, u, v)) return false;
if (aFirst) ans = {a[in].id, a[out].id, u.id, v.id};
else ans = {u.id, v.id, a[in].id, a[out].id};
return true;
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n;
vector<Pt> A(n);
for (int i = 0; i < n; ++i) cin >> A[i].x >> A[i].y, A[i].id = i + 1;
cin >> m;
vector<Pt> B(m);
for (int i = 0; i < m; ++i) cin >> B[i].x >> B[i].y, B[i].id = i + 1;
Hull HA = buildHull(A), HB = buildHull(B);
array<int, 4> ans{-1, -1, -1, -1};
if (mixedCase(A, HB, true, ans) || mixedCase(B, HA, false, ans)) {
cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << ' ' << ans[3] << '\n';
continue;
}
bool allAOut = true, allBOut = true;
for (Pt x : A) allAOut &= !inConvex(HB.p, x);
for (Pt x : B) allBOut &= !inConvex(HA.p, x);
Pt p, q, u, v;
if (allAOut && findOutsidePair(A, HB, p, q) && findHullHit(p, q, HB.p, u, v)) {
cout << p.id << ' ' << q.id << ' ' << u.id << ' ' << v.id << '\n';
} else if (allBOut && findOutsidePair(B, HA, p, q) && findHullHit(p, q, HA.p, u, v)) {
cout << u.id << ' ' << v.id << ' ' << p.id << ' ' << q.id << '\n';
} else {
cout << -1 << '\n';
}
}
}