t

from math import sqrt


class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return "<Point  x:{x}, y:{y}>".format(x=self.x, y=self.y)

    def distance(self, point):
        d = sqrt((self.x - point.x)**2 + (self.y - point.y)**2)
        return d


class Click(object):
    def __init__(self, point):
        self.point = point

    def __str__(self):
        return "<Click: point:{point}>".format(point=self.point)


class Region(object):
    count = 0

    def __init__(self, pointA, pointB):
        self.pointA = pointA
        self.pointB = pointB

        self.label = chr(ord('A') + Region.count)
        Region.count += 1

    def __str__(self):
        s = "<Region label:{label}," \
            " topleft:{pointA}, bottomright:{pointB}>".format(
            label=self.label, pointA=self.pointA, pointB=self.pointB
        )
        return s


class Icon(object):
    count = 0

    def __init__(self, pointI):
        self.pointI = pointI

        Icon.count += 1
        self.label = str(Icon.count)

    def __str__(self):
        return "<Icon label:{label}, pointI:{pointI}>".format(
            label=self.label, pointI=self.pointI
        )




def read_click(click_line):
    elements = click_line.split()
    p = Point(x=int(elements[1]), y=int(elements[2]))
    click = Click(point=p)
    return click


def read_icon(definition_line):
    elements = definition_line.split()
    p = Point(x=int(elements[1]), y=int(elements[2]))

    icon = Icon(pointI=p)
    return icon


def read_region(definition_line):
    elements = definition_line.split()
    pointA = Point(x=int(elements[1]), y=int(elements[2]))
    pointB = Point(x=int(elements[3]), y=int(elements[4]))

    region = Region(pointA=pointA, pointB=pointB)
    return region


def is_click_in_region(region, click):
    x1, y1 = region.pointA.x, region.pointA.y
    x2, y2 = region.pointB.x, region.pointB.y

    x, y = click.point.x, click.point.y

    if (x >= x1) and (x <= x2) and (y >= y1) and (y <= y2):
        return True

    return False



def get_region_of_click(all_regions, click):

    for region in reversed(all_regions):
        if is_click_in_region(region, click):
            return region

    return None

def get_closest_icons_for_click(all_icons, click):
    closest_icons = list()
    closest_distance = sqrt(2*(500**2)) + 1

    for icon in all_icons:
        distance_from_click = icon.pointI.distance(click.point)
        if distance_from_click < closest_distance:
            closest_icons = list()
            closest_icons.append(icon)
            closest_distance = distance_from_click
        elif distance_from_click == closest_distance:
            closest_icons.append(icon)

    return closest_icons



if __name__ == "__main__":

    all_regions = list()
    all_icons = list()
    all_clicks = list()


    with open('definitions.txt', 'r') as f:

        for line in f:
            if line.startswith("I"):
                icon = read_icon(line)
                all_icons.append(icon)
            elif line.startswith("R"):
                region = read_region(line)
                all_regions.append(region)


    with open('clicks.txt', 'r') as f:
        for line in f:
            if line.startswith("M"):
                click = read_click(line)
                all_clicks.append(click)

    print "-----All Regions----"
    for region in all_regions:
        print region

    print "-------All Icons-----"
    for icon in all_icons:
        print icon

    print "--------All clicks-----"
    for click in all_clicks:
        print click


    with open('output.txt', 'a') as f:

        print "------Regions of click"
        for click in all_clicks:
            region = get_region_of_click(all_regions, click)
            if region is not None:
                f.write(region.label + "\n")
            else:
                closest_icons = get_closest_icons_for_click(all_icons, click)
                s = ""
                for icon in closest_icons:
                    icon_str = '{:>3}'.format(77)
                    print icon_str
                    s += "{:>3}".format(icon.label)
                f.write(s + "\n")