bac_a_sable/2d_dichotomy.py

import math
import sys


w, h = [int(i) for i in input().split()]
# grid = [(x, y) for x in range(0, w) for y in range(0, h)]

grid = [[1 for _ in range(w)] for _ in range(h)]
NULL_ROW = [0 for _ in range(w)]


n = int(input())  # maximum number of turns before game over.
x0, y0 = [int(i) for i in input().split()]

# handle special case
if w + h <= 2:
    input()
    print("0 0")

DETECT = {"COLDER":-1, "WARMER": 1, "SAME": 0}

def distance(xa, ya, xb, yb):
    return math.hypot((xb - xa), (ya - yb))

def _centroid(data):
    xs, ys = zip(*data)
    return int(sum(xs) / len(xs)), int(sum(ys) / len(xs))

def centroid(table):
    yc = int(sum([y * sum(row) for y, row in enumerate(table)]) / sum(sum(table, [])))
    xc = int(sum([x * v for x, v in enumerate(table[yc])]) / sum(table[yc]))
    return xc, yc

def search2d(grid, _send, _get):
    # dichotomy on 3d list
    icur, jcur = x0, y0
    input()

    while 1:
        inew, jnew = centroid(grid)
        while not grid[jnew][inew]:
            inew = (inew + 1) % w
            jnew = (jnew + 1) % h

        # print("send new ", inew, jnew, file=sys.stderr)

        _send(inew, jnew)

        ddist = _get()
        # print("ddist= ", ddist, file=sys.stderr)
        if ddist > 0:
            grid = [[int(v == 1 and distance(i, j, inew, jnew) < distance(i, j, icur, jcur)) \
                    for i, v in enumerate(row)]  for j, row in enumerate(grid)]
        elif ddist < 0:
            grid = [[int(v == 1 and distance(i, j, inew, jnew) > distance(i, j, icur, jcur)) \
                    for i, v in enumerate(row)]  for j, row in enumerate(grid)]
        else:
            grid = [[int(v == 1 and distance(i, j, inew, jnew) == distance(i, j, icur, jcur)) \
                    for i, v in enumerate(row)]  for j, row in enumerate(grid)]

        # print("grid : ", grid, file=sys.stderr)
        if len(grid) == 1:
            return grid.pop()

        # remove the current cell
        grid[jcur][icur] = 0
        icur, jcur = inew, jnew


def old_search2d(grid, _send, _get):
    # dichotomy on 3d list
    x, y = x0, y0
    xnew, ynew = x, y
    input()
    if len(grid) == 1:
        return 0, 0

    while 1:
        imid = int(len(grid) / 2)
        # print("middle of ", grid, file=sys.stderr)

        while (xnew, ynew) == (x, y):
            try:
                xnew, ynew = grid[imid]
                imid = (imid + 1) % len(grid)
            except IndexError:
                pass

        # print("send new ", xnew, ynew, file=sys.stderr)

        _send(xnew, ynew)

        ddist = _get()
        # print("ddist= ", ddist, file=sys.stderr)
        if ddist > 0:
            grid = [(xc, yc) for xc, yc in grid if distance(xc, yc, xnew, ynew) < distance(xc, yc, x, y)]
        elif ddist < 0:
            grid = [(xc, yc) for xc, yc in grid if distance(xc, yc, xnew, ynew) > distance(xc, yc, x, y)]
        else:
            grid = [(xc, yc) for xc, yc in grid if distance(xc, yc, xnew, ynew) == distance(xc, yc, x, y)]

        # print("grid : ", grid, file=sys.stderr)
        if len(grid) == 1:
            return grid.pop()

        x, y = xnew, ynew

def get_data():
    return DETECT[input()]

def send_data(x, y):
    print("{} {}".format(x, y))

x, y = search2d(grid, send_data, get_data)