Problem:


Problem C: Simple GUI Application

Advanced Creative Mobile 社（ACM社）では、新しいポータブルコンピュータに搭載するGUIアプリケーションの開発を行うことになった。

下図に示すように、GUIは１つのメインパネルを持ち、その上にいくつかのパネルが配置され、さらにそれらのパネルの上にもいくつかのパネルが配置されるような入れ子構造になっている。パネルはすべて辺が座標軸に平行・垂直な長方形または正方形である。

アプリケーションはパネルの入れ子構造をタグ構造で保持する仕様となっている。パネルを表すタグ構造は、タグ値とそのパネルの上に配置されているパネルのタグ構造のリストを持つ。タグ値はそのパネルの左上の座標 (x1, y1) と 右下の座標 (x2, y2) を示す。

タグ構造の構文規則を以下に示す。ここで、構文の記述に用いる記号の意味を、以下の表のように定める。"<"、">", "," 及び "/" は、字句要素である。

記号意味

::=定義する

{}* { と } で囲まれた要素の 0 回以上の繰り返し

タグ構造 ::= 開始タグ タグ値 {タグ構造}* 終了タグ
開始タグ ::= <タグ名>
終了タグ ::= </タグ名>
タグ名   ::= 文字列
タグ値   ::= 整数,整数,整数,整数

タグ名はパネルの名前を示す１文字以上からなる文字列である。

タグ値は、カンマで区切られた４つの整数であり、それぞれパネルの座標を示す x1, y1, x2, y2 である。

例えば、上図に示したGUIは以下のタグ構造で記述される(スペースの関係上２行にまたがっているが、入力は１行で与えられる)：

<main>10,10,190,150<menu>20,20,70,140</menu><primary>80,20,180,140
<text>90,30,170,80</text><button>130,110,170,130</button></primary></main>

このGUIでは、ユーザがある点をタッチすると、その点において最上部にあるパネルが選択される（境界線を含む）。

あなたの仕事は、メインパネルのタグ構造と、タッチされた点のリストを読み込み、以下の情報を出力するプログラムを作成することである。

選択されたパネルの名前

そのパネルの直接上に配置されているパネルの数（以下"子の数"と呼ぶ）

なお、入力されるタグ構造について以下のことを仮定してよい。

タグ構造に文法エラーはない。

パネルがそれを含むパネル（以下"親パネル"と呼ぶ）からはみ出すことはなく、境界にも触れない。

同じ親パネルを持つパネル同士は重ならず、触れない。

同じ名前のパネルはない。

Input

入力は複数のデータセットからなる。各データセットは以下の形式で与えられる：

n
タグ構造
x1 y1
x2 y2
   .
   .
   .
xn yn

n はタッチされた点の数を示す整数である。タグ構造は空白を含まない１行の文字列である。xi, yi は i 番めにタッチされた点の x 座標と y 座標を表す（座標軸は上図に定めたものとする）。

n ≤ 100、タグ構造の文字列の長さ ≤ 1000 と仮定してよい。また、入力で与えられる x 座標 y 座標は 0 以上 10,000 以下と仮定してよい。

n が 0 のとき入力の終わりとする。

Output

各データセットに対して、選択された順番にパネルの名前と子の数を出力せよ。各名前と子の数を１つの空白で区切って１行に出力せよ。何も選択されない場合（タッチされた点にパネルがない場合）は、"OUT OF MAIN PANEL 1"と出力せよ。

Sample Input

5
<main>10,10,190,150<menu>20,20,70,140</menu><primary>80,20,180,140</primary></main>
10 10
15 15
40 60
2 3
130 80
0

Output for the Sample Input

main 2
main 2
menu 0
OUT OF MAIN PANEL 1
primary 0



Sample input:
5
<main>10,10,190,150<menu>20,20,70,140</menu><primary>80,20,180,140</primary></main>
10 10
15 15
40 60
2 3
130 80
0


Sample output:
main 2
main 2
menu 0
OUT OF MAIN PANEL 1
primary 0

Submission status: Accepted

Solution code:
class Panel(object):
    def __init__(self, name, depth, child, x1, y1, x2, y2):
        self.name = name
        self.depth = depth
        self.child = child
        self.x1 = x1
        self.y1 = y1
        self.x2 = x2
        self.y2 = y2

    def touch(self, x, y, depth):
        if depth < self.depth and self.x1 <= x <= self.x2 and self.y1 <= y <= self.y2:
            return self
        else:
            return None

    def __repr__(self):
        return f"{self.name} {self.child}"


def solve():
    import re
    while True:
        N = int(input())
        if N == 0:
            break

        S = input()
        panels = [Panel("OUT OF MAIN PANEL", 0, 1, 0, 0, 10000, 10000)]

        def rec(s, depth):
            child = 0
            while s:
                child += 1
                tag_name = re.match(r"<([^>]+)>", s).group(1)
                result = re.match(r"<%s>(\d+),(\d+),(\d+),(\d+)(.*?)</%s>" % (tag_name, tag_name), s)
                panels.append(Panel(tag_name, depth, rec(result.group(5), depth + 1), *(map(int, result.groups()[:4]))))
                s = s[result.span()[1]:]
            return child

        rec(S, 1)

        for _ in [0]*N:
            x, y = map(int, input().split())
            result = panels[0]
            for panel in panels[1:]:
                result = panel.touch(x, y, result.depth) or result
            print(result)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
class Panel:
    def __init__(self, name, points, children):
        self.name = name
        self.x1 = points[0]
        self.x2 = points[2]
        self.y1 = points[1]
        self.y2 = points[3]
        self.children = children
        self.child_cnt = len(children)

    def search(self, x, y):
        if not (self.x1 <= x <= self.x2 and self.y1 <= y <= self.y2):
            return ["OUT", "OF", "MAIN", "PANEL", "1"]
        for child in self.children:
            if child.x1 <= x <= child.x2 and child.y1 <= y <= child.y2:
                return child.search(x, y)
        return self.name, self.child_cnt


def parse_tag_structure(s, pointer):
    name, pointer = parse_begin_tag(s, pointer)
    points, pointer = parse_tag_value(s, pointer)
    children = []
    while True:
        if s[pointer + 1] == "/":break
        child, pointer = parse_tag_structure(s, pointer)
        children.append(child)
    pointer = parse_end_tag(s, pointer)
    return Panel(name, points, children), pointer


def parse_begin_tag(s, pointer):
    pointer += 1
    name = ""
    while s[pointer] != ">":
        name += s[pointer]
        pointer += 1
    pointer += 1
    return name, pointer


def parse_tag_value(s, pointer):
    points = []
    for _ in range(4):
        point = ""
        while "0" <= s[pointer] <= "9":
            point += s[pointer]
            pointer += 1
        points.append(int(point))
        pointer += 1
    return points, pointer - 1


def parse_end_tag(s, pointer):
    while s[pointer] != ">":
        pointer += 1
    pointer += 1
    return pointer


while True:
    n = int(input())
    if n == 0:break
    s = input()
    panel, _ = parse_tag_structure(s, 0)
    for _ in range(n):
        x, y = map(int, input().split())
        print(*panel.search(x, y))