#!/usr/bin/env python3 # GPT Interactive solution : 2-D rectangle queries (≤ 8000) to locate ≤ 100 points (0-1e6) import sys from collections import deque # ----- parameters ------------------------------------------------------------ COORD_MIN = 0 COORD_MAX = 1_000_000 QUERY_LIMIT = 8000 # ----------------------------------------------------------------------------- query_cnt = 0 # 送信した質問数 points = [] # 発見した (x, y) # ────────────────────────────────────────────────────────────────────────────── def ask(x1: int, x2: int, y1: int, y2: int) -> bool: """ 1 回質問する.矩形 [x1,x2] × [y1,y2] 内に点が存在すれば True を返す. ジャッジが -1 を返した場合は即座に exit(0) する. """ global query_cnt if query_cnt >= QUERY_LIMIT: sys.exit(0) # これ以上質問するとペナルティなので強制終了 print(x1, x2, y1, y2, flush=True) query_cnt += 1 try: resp = int(sys.stdin.readline()) except Exception: sys.exit(0) # 想定外の入力 ⇒ 終了 if resp == -1: # 不正クエリ / 回数超過 sys.exit(0) return resp == 1 # 1 → 存在する, 0 → 無い # ────────────────────────────────────────────────────────────────────────────── def main() -> None: # 最初の矩形 ([全域]) に点が存在するのは制約 N ≥ 1 で保証されているので, # 根ノードの存在判定クエリは不要. 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() # 既に一点に絞られたら記録 if x1 == x2 and y1 == y2: points.append((x1, y1)) # 100 個そろえば終了してもよいが,キューが空になるまで走らせても # 問題ない(重複座標は無いことが保証されている) 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(-1, flush=True) # これ以降は答えの出力 print(len(points), flush=True) for x, y in points: print(x, y, flush=True) if __name__ == "__main__": main()