// 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. #include #include #include #include using namespace std; using P = pair; 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; map l{{-1000, -2000000}, {1, 1}, {w, 1}, {w + 1000, -2000000}}, u{{0, 3000000}, {1, h}, {w, h}, {w + 1, 3000000}}; 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(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(next(it)) != l.end()) { auto A = *next(it); auto B = *next(next(it)); if(area(A, B, p) < 0) break; l.erase(next(it)); } }; auto add_upper = [&](long long x, long long y) { P p{x, y}; auto it = u.insert_or_assign(x, y).first; // left of x while(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(next(it)) != u.end()) { auto A = *next(it); auto B = *next(next(it)); if(area(A, B, p) > 0) break; u.erase(next(it)); } }; 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; }