#include #include #include #include // #include #include #include #include #include using namespace std; #define x first #define y second typedef pair ii; int w, h; int nqueries_used = 0; ii horizon_pt(0, 0); int Query(int x, int y) { static map cache; if (cache.find(ii(x, y)) != cache.end()) return cache[ii(x, y)]; nqueries_used++; printf("? %d %d\n", x, y); fflush(stdout); char ans[10]; scanf("%s", ans); int res; if (ans[1] == 'k') // sky res = 1; else if (ans[1] == 'e') // sea res = -1; else if (ans[1] == 'o') { // horizon if (horizon_pt == ii(0, 0)) { horizon_pt = ii(x, y); } else { assert(horizon_pt != ii(x, y)); fprintf(stderr, "# queries used = %d\n", nqueries_used); printf("! %d %d %d %d\n", horizon_pt.first, horizon_pt.second, x, y); fflush(stdout); exit(0); } res = 0; } else { exit(1); } return cache[ii(x, y)] = res; } pair find_height(int xcoord) { int lo = 1, hi = h; while (hi - lo > 1) { int mi = (lo+hi)/2; int res = Query(xcoord, mi); if (res == 0) return make_pair(mi, mi); (res > 0 ? hi : lo) = mi; } return make_pair(lo, hi); } int main() { // srand(time(NULL)); scanf("%d%d", &w, &h); auto [y1L, y1R] = find_height(1); auto [y2L, y2R] = find_height(w); vector pts; for (int x = 2; x < w; x++) { for (int y = 1; y <= h; y++) { // 2 conditions needed: // y <= y1R + (x-1)/(w-1) * (y2R - y1R) // y >= y1L + (x-1)/(w-1) * (y2L - y1L) if ((y - y1R) * (w-1) > (x-1) * (y2R - y1R)) continue; if ((y - y1L) * (w-1) < (x-1) * (y2L - y1L)) continue; pts.emplace_back(x, y); } } sort(begin(pts), end(pts)); // is point (x,y) below the line p1 -- p2? auto below = [&] (int x, int y, ii p1, ii p2) -> bool { return (y - p1.y) * (p2.x - p1.x) <= (x - p1.x) * (p2.y - p1.y); }; auto above = [&] (int x, int y, ii p1, ii p2) -> bool { return (y - p1.y) * (p2.x - p1.x) >= (x - p1.x) * (p2.y - p1.y); }; if (horizon_pt == ii(0, 0)) { set cands; map> connected; for (ii p1 : pts) for (ii p2 : pts) { if (p1.x >= p2.x) continue; if (below(1, y1L, p1, p2) && above(1, y1R, p1, p2) && below(w, y2L, p1, p2) && above(w, y2R, p1, p2)) { cands.insert(p1); cands.insert(p2); connected[p1].push_back(p2); connected[p2].push_back(p1); } } vector candsV(begin(cands), end(cands)); // random_shuffle(begin(candsV), end(candsV)); for (auto p : candsV) if (Query(p.x, p.y) == 0) { for (auto p2 : connected[p]) Query(p2.x, p2.y); } } // Better approach? There is a bug here: /* vector pts2; for (unsigned int i = 0; i < pts.size(); i++) { bool valid = false; if (y1L == y1R) { valid = below(w, y2L, pts[i], ii(1, y1L)) && above(w, y2R, pts[i], ii(1, y1L)); } else if (y2L == y2R) { valid = below(w, y1L, pts[i], ii(w, y2L)) && above(w, y1R, pts[i], ii(w, y2L)); } else { for (unsigned int j = 0; j < pts.size(); j++) { if (j == i || pts[i].x == pts[j].x) continue; // calculate intersection point at x=1: if (below(1, y1L, pts[i], pts[j]) && above(1, y1R, pts[i], pts[j]) && below(w, y2L, pts[i], pts[j]) && above(w, y2R, pts[i], pts[j])) { valid = true; break; } } } if (valid) pts2.push_back(pts[i]); } for (auto [x,y] : pts2) fprintf(stderr, "%d %d\n", x, y); printf("! 1 1 2 2\n"); fflush(stdout); exit(0); if (pts.size() > 800) pts = pts2; */ // Naive approach: // random_shuffle(begin(pts), end(pts)); for (auto [x,y] : pts) Query(x, y); assert(false); return 0; }