#!/usr/bin/env python3 # 2-D interactive search (≤ 100 points) with ≤ 8000 rectangle queries. # protocol: "? x1 x2 y1 y2" ←→ judge: 1 / 0 / -1 # "! N" → judge: expects N lines "Xi Yi" import sys from collections import deque # ───── 定数 ─────────────────────────────────────── MIN_C, MAX_C = 0, 1_000_000 # 座標範囲 QUERY_LIMIT = 8000 # 上限クエリ数 # ──────────────────────────────────────────────── query_cnt = 0 # 送信したクエリ数 points = [] # 発見した点 # ───── 質問関数 ───────────────────────────────── def ask(x1: int, x2: int, y1: int, y2: int) -> bool: """ 矩形 [x1,x2] × [y1,y2] に少なくとも 1 点が存在するかを尋ねる。 True なら存在、False なら存在しない。 """ global query_cnt if query_cnt >= QUERY_LIMIT: sys.exit(0) # これ以上は違反 print(f"? {x1} {x2} {y1} {y2}", flush=True) query_cnt += 1 resp_line = sys.stdin.readline() if not resp_line: sys.exit(0) # EOF resp = int(resp_line) if resp == -1: # 不正・回数超過通知 sys.exit(0) return resp == 1 # ──────────────────────────────────────────────── def main() -> None: # 四分木探索:必ず 1 点以上含む矩形だけをキューに保持 q: deque[tuple[int, int, int, int]] = deque( [(MIN_C, MAX_C, MIN_C, MAX_C)] ) while q: x1, x2, y1, y2 = q.pop() # 1 格子点に確定 if x1 == x2 and y1 == y2: points.append((x1, y1)) continue # 長い辺方向を 2 分割 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()