#!/usr/bin/env python3 # GPT Interactive solution with '? / !' protocol # 2-D rectangle queries (≤ 8000) to locate ≤ 100 unknown points (0-1e6) import sys from collections import deque # ────────── 問題定数 ───────────────────────────── COORD_MIN = 0 COORD_MAX = 1_000_000 QUERY_LIMIT = 8000 # ──────────────────────────────────────────────── query_cnt = 0 # 送信済みクエリ数 points = [] # 発見した点 (x, y) # ────────── 1 回問い合わせる関数 ──────────────── def ask(x1: int, x2: int, y1: int, y2: int) -> bool: """ 矩形 [x1,x2]×[y1,y2] に点が存在するか質問し, True / False を返す. """ global query_cnt if query_cnt >= QUERY_LIMIT: sys.exit(0) # これ以上は TLE/WA になるので終了 # '?' プレフィックス print(f"? {x1} {x2} {y1} {y2}", flush=True) query_cnt += 1 ans_line = sys.stdin.readline() if not ans_line: sys.exit(0) # EOF ⇒ 終了 ans = int(ans_line) if ans == -1: # 不正・上限超過 sys.exit(0) return ans == 1 # ──────────────────────────────────────────────── def main() -> None: # 四分木(大きい辺方向を常に半分)で分割探索 q: deque[tuple[int, int, int, int]] = deque() q.append((COORD_MIN, COORD_MAX, COORD_MIN, COORD_MAX)) while q: x1, x2, y1, y2 = q.pop() # 1 点に確定 if x1 == x2 and y1 == y2: points.append((x1, y1)) continue # 長いほうを分割 if (x2 - x1) >= (y2 - y1): xm = (x1 + x2) // 2 # 左 if ask(x1, xm, y1, y2): q.append((x1, xm, y1, y2)) # 右 if xm + 1 <= x2 and ask(xm + 1, x2, y1, y2): q.append((xm + 1, x2, y1, y2)) else: ym = (y1 + y2) // 2 # 下 if ask(x1, x2, y1, ym): q.append((x1, x2, y1, ym)) # 上 if ym + 1 <= y2 and ask(x1, x2, ym + 1, y2): q.append((x1, x2, ym + 1, y2)) # ───── 全点発見 ─────────────────────────── print(f"! {len(points)}", flush=True) for x, y in points: print(f"{x} {y}", flush=True) if __name__ == "__main__": main()