iou.py

#!/usr/bin/python3

## Input:
# 3 3
# 6 7 9
# 2 8 1
# 3 4 4
# 2
# 0 0 1 1 1 1 2 2
# 0 0 2 2 0 2 1 2

import sys
import numpy as np

def read_stdin():
    for line in sys.stdin:
        yield [int(x) for x in line.split()]

def get_inputs():
    reader = read_stdin()

    def next_input():
        rows = next(reader)[0]
        mat = np.vstack([next(reader) for _ in range(rows)])

        num_queries = next(reader)[0]
        queries = []
        for _ in range(num_queries):
            query_line = next(reader)
            queries.append((query_line[:4], query_line[4:]))
        return mat, queries

    while True:
        try:
            yield next_input()
        except StopIteration:
            return

def get_intersection(r1, r2):
    return [
        max(r1[0], r2[0]),
        max(r1[1], r2[1]),
        min(r1[2], r2[2]),
        min(r1[3], r2[3]),
    ]

def lookup(mat, cache, x, y):
    if x < 0 or y < 0:
        return 0
    if cache[x, y] == -1:
        cache[x, y] = mat[x, y] + lookup(mat, cache, x-1, y) \
                + lookup(mat, cache, x, y-1) - lookup(mat, cache, x-1, y-1)
    return cache[x, y]

def get_area(r, mat, cache):
    x1, y1, x2, y2 = r
    if x1 > x2 or y1 > y2:
        return 0
    return lookup(mat, cache, x2, y2) - lookup(mat, cache, x1-1, y2) \
            - lookup(mat, cache, x2, y1-1) + lookup(mat, cache, x1-1, y1-1)

def solve(mat, queries):
    cache = np.full(mat.shape, -1)
    for r1, r2 in queries:
        r_int = get_intersection(r1, r2)
        area1 = get_area(r1, mat, cache)
        area2 = get_area(r2, mat, cache)
        area_int = get_area(r_int, mat, cache)
        if area1 == 0 and area2 == 0:
            iou = 0
        else:
            iou = area_int / (area1 + area2 - area_int)
        print(iou)

if __name__ == '__main__':
    for mat, queries in get_inputs():
        solve(mat, queries)