// Keep an upper and lower convex hull of the queries sea and sky points. // Randomly query any point not in one of these hulls and update them. // // Difference to ragnar-randomized-convex-hull.cpp: // The lower and upper hulls interact with each other in a special way. // Whenever we add a point to the upper hull, we can grow the lower hull to // include all points for which the straight line to X crosser the lower hull. #include #include #include #include #include using namespace std; using P = pair; P operator-(P l, P r) { return {l.first - r.first, l.second - r.second}; } long long dot(P p, P q) { return p.first * q.second - p.second * q.first; } long long area(P p, P q, P r) { return dot(p, q) + dot(q, r) + dot(r, p); } int main() { long long w, h; cin >> w >> h; // srand(time(0)); map l{{1, 1}, {w, 1}}, u{{1, h}, {w, h}}; auto upper = [&](long long x) { auto it = u.lower_bound(x); if(it->first == x) return it->second; P n = *it; P p = *prev(it); if(n.second < p.second) swap(n, p); return p.second + ((n.second - p.second) * (x - p.first) + n.first - p.first - 1) / (n.first - p.first); }; auto lower = [&](long long x) { auto it = l.lower_bound(x); if(it->first == x) return it->second; P n = *it; P p = *prev(it); if(n.second < p.second) swap(n, p); return p.second + (n.second - p.second) * (x - p.first) / (n.first - p.first); }; vector

ans; auto random_point = [&] { long long x; do { x = rand() % w + 1; } while(upper(x) == lower(x) + 1 or (!ans.empty() and ans[0].first == x)); long long y = rand() % (upper(x) - lower(x) - 1) + lower(x) + 1; assert(y > lower(x)); return P{x, y}; }; while(ans.size() < 2) { auto [qx, qy] = random_point(); cout << "? " << qx << ' ' << qy << endl; string s; cin >> s; auto add_lower = [&](long long x, long long y) { P p{x, y}; auto it = l.insert_or_assign(x, y).first; // left of x while(it != l.begin() and prev(it) != l.begin()) { auto A = *prev(it); auto B = *prev(prev(it)); if(area(A, B, p) > 0) break; l.erase(prev(it)); } // right while(next(it) != l.end() and next(next(it)) != l.end()) { auto A = *next(it); auto B = *next(next(it)); if(area(A, B, p) < 0) break; l.erase(next(it)); } // Upgrade leading parts of upper hull. while(x > 1) { auto A = *begin(u); auto B = *next(begin(u)); if(B.first < p.first and area(A, B, p) >= 0) { u.erase(u.begin()); } else { // Extrapolate X-A backwards. P q = A; assert(A.first < p.first); while(q.first > 0) q = q - (p - A); u.insert(q); break; } } // Upgrade trailing parts of upper hull. while(x < w) { auto A = *prev(end(u)); auto B = *prev(prev(end(u))); if(B.first > p.first and area(A, B, p) <= 0) { u.erase(prev(u.end())); } else { // Extrapolate X-A forwards. P q = A; assert(A.first > p.first); while(q.first <= w) q = q - (p - A); u.insert(q); break; } } }; auto add_upper = [&](long long x, long long y) { // cerr << "ADD UPPER " << x << " " << y << endl; P p{x, y}; auto it = u.insert_or_assign(x, y).first; // left of x while(it != u.begin() and prev(it) != u.begin()) { auto A = *prev(it); auto B = *prev(prev(it)); if(area(A, B, p) < 0) break; u.erase(prev(it)); } // right while(next(it) != u.end() and next(next(it)) != u.end()) { auto A = *next(it); auto B = *next(next(it)); if(area(A, B, p) > 0) break; u.erase(next(it)); } // Upgrade leading parts of lower hull. while(x > 1) { auto A = *begin(l); auto B = *next(begin(l)); if(B.first < p.first and area(A, B, p) <= 0) { l.erase(l.begin()); } else { // Extrapolate X-A backwards. P q = A; assert(A.first < p.first); while(q.first > 0) q = q - (p - A); l.insert(q); break; } } // Upgrade trailing parts of lower hull. while(x < w) { auto A = *prev(end(l)); auto B = *prev(prev(end(l))); if(B.first > p.first and area(A, B, p) >= 0) { l.erase(prev(l.end())); } else { // Extrapolate X-A forwards. P q = A; assert(A.first > p.first); while(q.first <= w) q = q - (p - A); l.insert(q); break; } } }; if(s == "horizon") { ans.emplace_back(qx, qy); add_lower(qx, qy - 1); add_upper(qx, qy + 1); } if(s == "sea") add_lower(qx, qy); if(s == "sky") add_upper(qx, qy); } cout << "! " << ans[0].first << ' ' << ans[0].second << ' ' << ans[1].first << ' ' << ans[1].second; }