Problem:


Problem H: Monster Trap

Once upon a time when people still believed in magic, there was a great wizard Aranyaka
Gondlir. After twenty years of hard training in a deep forest, he had finally mastered ultimate
magic, and decided to leave the forest for his home.

Arriving at his home village, Aranyaka was very surprised at the extraordinary desolation. A
gloom had settled over the village. Even the whisper of the wind could scare villagers. It was a
mere shadow of what it had been.

What had happened? Soon he recognized a sure sign of an evil monster that is immortal. Even
the great wizard could not kill it, and so he resolved to seal it with magic. Aranyaka could cast
a spell to create a monster trap: once he had drawn a line on the ground with his magic rod,
the line would function as a barrier wall that any monster could not get over. Since he could
only draw straight lines, he had to draw several lines to complete a monster trap, i.e., magic
barrier walls enclosing the monster. If there was a gap between barrier walls, the monster could
easily run away through the gap.

For instance, a complete monster trap without any gaps is built by the barrier walls in the left
figure, where “M” indicates the position of the monster. In contrast, the barrier walls in the
right figure have a loophole, even though it is almost complete.

Your mission is to write a program to tell whether or not the wizard has successfully sealed the
monster.

Input

The input consists of multiple data sets, each in the following format.

n
x1 y1  x'1 y'1
x2 y2  x'2 y'2
      ...
xn yn  x'n y'n

The first line of a data set contains a positive integer n, which is the number of the line segments
drawn by the wizard. Each of the following n input lines contains four integers x, y, x', and
y', which represent the x- and y-coordinates of two points (x, y) and (x', y' ) connected by a line
segment. You may assume that all line segments have non-zero lengths. You may also assume
that n is less than or equal to 100 and that all coordinates are between -50 and 50, inclusive.

For your convenience, the coordinate system is arranged so that the monster is always on the
origin (0, 0). The wizard never draws lines crossing (0, 0).

You may assume that any two line segments have at most one intersection point and that no
three line segments share the same intersection point. You may also assume that the distance
between any two intersection points is greater than 10-5.

An input line containing a zero indicates the end of the input.

Output

For each data set, print “yes” or “no” in a line. If a monster trap is completed, print “yes”.
Otherwise, i.e., if there is a loophole, print “no”.

Sample Input

8
-7 9 6 9
-5 5 6 5
-10 -5 10 -5
-6 9 -9 -6
6 9 9 -6
-1 -2 -3 10
1 -2 3 10
-2 -3 2 -3
8
-7 9 5 7
-5 5 6 5
-10 -5 10 -5
-6 9 -9 -6
6 9 9 -6
-1 -2 -3 10
1 -2 3 10
-2 -3 2 -3
0

Output for the Sample Input

yes
no



Sample input:
8
-7 9 6 9
-5 5 6 5
-10 -5 10 -5
-6 9 -9 -6
6 9 9 -6
-1 -2 -3 10
1 -2 3 10
-2 -3 2 -3
8
-7 9 5 7
-5 5 6 5
-10 -5 10 -5
-6 9 -9 -6
6 9 9 -6
-1 -2 -3 10
1 -2 3 10
-2 -3 2 -3
0


Sample output:
yes
no

Submission status: Accepted

Solution code:
def string_to_complex(s):
    a, b, c, d = map(int, s.split())
    return (a + b * 1j, c + d * 1j)

def dot(c1, c2):
    return c1.real * c2.real + c1.imag * c2.imag

def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def cross_point(p1, p2, p3, p4):
    crs1 = cross(p2 - p1, p3 - p1)
    crs2 = cross(p2 - p1, p4 - p1)
    if crs1 == 0 and crs2 == 0:
        if p1 == p3 or p1 == p4:
            return p1
        elif p2 == p3 or p2 == p4:
            return p2
        else:
            return None
    crs3 = cross(p4 - p3, p1 - p3)
    crs4 = cross(p4 - p3, p2 - p3)
    if crs1 * crs2 <= 0 and crs3 * crs4 <= 0:
        base = p4 - p3
        hypo1 = p1 - p3
        hypo2 = p2 - p3
        d1 = abs(cross(base, hypo1)) / abs(base)
        d2 = abs(cross(base, hypo2)) / abs(base)
        return p1 + d1 / (d1 + d2) * (p2 - p1)
    else:
        return None

def contain(polygon):
    flag = False
    for a, b in zip(polygon[0:], polygon[1:] + [polygon[0]]):
        if a.imag > b.imag:
            a, b = b, a
        if a.imag <= 0 and b.imag > 0 and cross(a, b) > 0:
            flag = not flag
    return flag

def solve():
    def dfs_contain(goal, edges, cross_points):
        cur_edge = edges[-1]
        for next_edge, next_cp in adj_edge[cur_edge]:
            if next_edge == goal:
                if contain(cross_points + [next_cp]):
                    break
            elif next_edge not in edges and unchecked[next_edge] and DP[next_edge]:
                edges.append(next_edge)
                cross_points.append(next_cp)
                if dfs_contain(goal, edges, cross_points):
                    break
                e = edges.pop()
                DP[e] = False
                cross_points.pop()
        else:
            return False
        return True
            
    from sys import stdin
    lines = stdin.readlines()
    
    from itertools import combinations
    
    while True:
        n = int(lines[0])
        if n == 0:
            break
        
        edges = enumerate(map(string_to_complex, lines[1:1+n]))
        adj_edge = [[] for i in range(n)]
        
        for e1, e2 in combinations(edges, 2):
            n1, t1 = e1
            n2, t2 = e2
            cp = cross_point(*t1, *t2)
            if cp:
                adj_edge[n1].append((n2, cp))
                adj_edge[n2].append((n1, cp))
        
        flag = True
        while flag:
            for i, ae in enumerate(adj_edge):
                if len(ae) == 1:
                    ne, cp = ae.pop()
                    adj_edge[ne].remove((i, cp))
                    break
            else:
                flag = False
        
        unchecked = [True] * n
        
        for e in range(n):
            unchecked[e] = False
            DP = [True] * n
            if dfs_contain(e, [e], []):
                print('yes')
                break
        else:
            print('no')
        
        del lines[:1+n]

solve()

Submission status: Accepted

Solution code:
def string_to_complex(s):
    a, b, c, d = map(int, s.split())
    return (a + b * 1j, c + d * 1j)

def dot(c1, c2):
    return c1.real * c2.real + c1.imag * c2.imag

def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def cross_point(p1, p2, p3, p4):
    crs1 = cross(p2 - p1, p3 - p1)
    crs2 = cross(p2 - p1, p4 - p1)
    if crs1 == 0 and crs2 == 0:
        if p1 == p3 or p1 == p4:
            return p1
        elif p2 == p3 or p2 == p4:
            return p2
        else:
            return None
    crs3 = cross(p4 - p3, p1 - p3)
    crs4 = cross(p4 - p3, p2 - p3)
    if crs1 * crs2 <= 0 and crs3 * crs4 <= 0:
        base = p4 - p3
        hypo1 = p1 - p3
        hypo2 = p2 - p3
        d1 = abs(cross(base, hypo1)) / abs(base)
        d2 = abs(cross(base, hypo2)) / abs(base)
        return p1 + d1 / (d1 + d2) * (p2 - p1)
    else:
        return None

def contain(polygon):
    flag = False
    for a, b in zip(polygon[0:], polygon[1:] + [polygon[0]]):
        if a.imag > b.imag:
            a, b = b, a
        if a.imag <= 0 and b.imag > 0 and cross(a, b) > 0:
            flag = not flag
    return flag

def solve():
    def dfs_contain(goal, edges, cross_points):
        cur_edge = edges[-1]
        for next_edge, next_cp in adj_edge[cur_edge]:
            if next_edge == goal:
                if contain(cross_points + [next_cp]):
                    break
            elif next_edge not in edges and DP[next_edge]:
                edges.append(next_edge)
                cross_points.append(next_cp)
                if dfs_contain(goal, edges, cross_points):
                    break
                e = edges.pop()
                DP[e] = False
                cross_points.pop()
        else:
            return False
        return True
            
    from sys import stdin
    lines = stdin.readlines()
    
    from itertools import combinations
    
    while True:
        n = int(lines[0])
        if n == 0:
            break
        
        edges = enumerate(map(string_to_complex, lines[1:1+n]))
        adj_edge = [[] for i in range(n)]
        
        for e1, e2 in combinations(edges, 2):
            n1, t1 = e1
            n2, t2 = e2
            cp = cross_point(*t1, *t2)
            if cp:
                adj_edge[n1].append((n2, cp))
                adj_edge[n2].append((n1, cp))
        
        flag = True
        while flag:
            for i, ae in enumerate(adj_edge):
                if len(ae) == 1:
                    ne, cp = ae.pop()
                    adj_edge[ne].remove((i, cp))
                    break
            else:
                flag = False
        
        for e in range(n):
            DP = [False] * e + [True] * (n - e)
            if dfs_contain(e, [e], []):
                print('yes')
                break
        else:
            print('no')
        
        del lines[:1+n]

solve()

Submission status: Accepted

Solution code:
def string_to_complex(s):
    a, b, c, d = map(int, s.split())
    return (a + b * 1j, c + d * 1j)

def dot(c1, c2):
    return c1.real * c2.real + c1.imag * c2.imag

def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def cross_point(p1, p2, p3, p4):
    crs1 = cross(p2 - p1, p3 - p1)
    crs2 = cross(p2 - p1, p4 - p1)
    if crs1 == 0 and crs2 == 0:
        if p1 == p3 or p1 == p4:
            return p1
        elif p2 == p3 or p2 == p4:
            return p2
        else:
            return None
    crs3 = cross(p4 - p3, p1 - p3)
    crs4 = cross(p4 - p3, p2 - p3)
    if crs1 * crs2 <= 0 and crs3 * crs4 <= 0:
        base = p4 - p3
        hypo1 = p1 - p3
        hypo2 = p2 - p3
        d1 = abs(cross(base, hypo1)) / abs(base)
        d2 = abs(cross(base, hypo2)) / abs(base)
        return p1 + d1 / (d1 + d2) * (p2 - p1)
    else:
        return None

def contain(polygon):
    flag = False
    for a, b in zip(polygon[0:], polygon[1:] + [polygon[0]]):
        if a.imag > b.imag:
            a, b = b, a
        if a.imag <= 0 and b.imag > 0 and cross(a, b) > 0:
            flag = not flag
    return flag

from cmath import phase, pi

def complex_compare_key(c):
    return (c.real, c.imag)

def complex_compare_key2(c):
    return c.real

def pos_phase(base, c1, c2):
    p = phase((c2 - base) / (c1 - base))
    if p < 0:
        p += 2 * pi
    return p

def solve():
    from sys import stdin
    lines = stdin.readlines()
    
    from itertools import combinations
    
    while True:
        n = int(lines[0])
        if n == 0:
            break
        
        edges = enumerate(map(string_to_complex, lines[1:1+n]))
        adj_edge_cp = [[] for i in range(n)]
        adj_cross_point = {}
        
        for e1, e2 in combinations(edges, 2):
            n1, t1 = e1
            n2, t2 = e2
            cp = cross_point(*t1, *t2)
            if cp:
                adj_edge_cp[n1].append(cp)
                adj_edge_cp[n2].append(cp)
                adj_cross_point[cp] = (n1, n2)
        
        for cp_list in adj_edge_cp:
            cp_list.sort(key=complex_compare_key)
        
        # creating adjacency list of intersection points
        for cp, t in adj_cross_point.items():
            e1, e2 = t
            e1_cp = adj_edge_cp[e1]
            e2_cp = adj_edge_cp[e2]
            cp_l = []
            if len(e1_cp) == 1:
                pass
            else:
                if cp == e1_cp[0]:
                    cp_l.append(e1_cp[1])
                elif cp == e1_cp[-1]:
                    cp_l.append(e1_cp[-2])
                else:
                    cp_idx = e1_cp.index(cp)
                    cp_l.append(e1_cp[cp_idx - 1])
                    cp_l.append(e1_cp[cp_idx + 1])
            if len(e2_cp) == 1:
                pass
            else:
                if cp == e2_cp[0]:
                    cp_l.append(e2_cp[1])
                elif cp == e2_cp[-1]:
                    cp_l.append(e2_cp[-2])
                else:
                    cp_idx = e2_cp.index(cp)
                    cp_l.append(e2_cp[cp_idx - 1])
                    cp_l.append(e2_cp[cp_idx + 1])
            adj_cross_point[cp] = cp_l
        
        # branch cut operation
        flag = True
        while flag:
            for cp, cp_list in adj_cross_point.items():
                if len(cp_list) == 1:
                    next_cp = cp_list.pop()
                    adj_cross_point[next_cp].remove(cp)
                    break
            else:
                flag = False
        
        del_cp_list = []
        for cp, cp_list in adj_cross_point.items():
            if not cp_list:
                del_cp_list.append(cp)
        for cp in del_cp_list:
            del adj_cross_point[cp]
        
        # polygon trace with left(right)-hand method
        cp_list = list(adj_cross_point)
        cp_list.sort(key=complex_compare_key2)
        visited = dict(zip(cp_list, [False] * len(cp_list)))
        for start in cp_list:
            if start.real >= 0:
                print("no")
                break
            if visited[start]:
                continue
            visited[start] = True
            path = [start - 1, start]
            flag = True
            while flag:
                pre_cp = path[-2]
                cp = path[-1]
                ang = 2 * pi
                for p in adj_cross_point[cp]:
                    if p == pre_cp:
                        continue
                    new_ang = pos_phase(cp, pre_cp, p)
                    if new_ang < ang:
                        next_cp = p
                        ang = new_ang
                visited[next_cp] = True
                if next_cp == start:
                    if contain(path[1:]):
                        print("yes")
                        flag = False
                    else:
                        break
                else:
                    path.append(next_cp)
            else:
                break
        else:
            print("no")
        
        del lines[:1+n]

solve()

Submission status: Runtime Error

Solution code:
def string_to_complex(s):
    a, b, c, d = map(int, s.split())
    return (a + b * 1j, c + d * 1j)

def dot(c1, c2):
    return c1.real * c2.real + c1.imag * c2.imag

def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def cross_point(p1, p2, p3, p4):
    crs1 = cross(p2 - p1, p3 - p1)
    crs2 = cross(p2 - p1, p4 - p1)
    if crs1 == 0 and crs2 == 0:
        if p1 == p3 or p1 == p4:
            return p1
        elif p2 == p3 or p2 == p4:
            return p2
        else:
            return None
    crs3 = cross(p4 - p3, p1 - p3)
    crs4 = cross(p4 - p3, p2 - p3)
    if crs1 * crs2 <= 0 and crs3 * crs4 <= 0:
        base = p4 - p3
        hypo1 = p1 - p3
        hypo2 = p2 - p3
        d1 = abs(cross(base, hypo1)) / abs(base)
        d2 = abs(cross(base, hypo2)) / abs(base)
        return p1 + d1 / (d1 + d2) * (p2 - p1)
    else:
        return None

def contain(polygon):
    flag = False
    for a, b in zip(polygon[0:], polygon[1:] + [polygon[0]]):
        if a.imag > b.imag:
            a, b = b, a
        if a.imag <= 0 and b.imag > 0 and cross(a, b) > 0:
            flag = not flag
    return flag

def solve():
    def dfs_contain(goal, edges, cross_points):
        cur_edge = edges[-1]
        for next_edge, next_cp in adj_edge[cur_edge]:
            if next_edge == goal:
                if contain(cross_points + [next_cp]):
                    break
            elif next_edge not in edges and unchecked[next_edge] and DP[next_edge]:
                edges.append(next_edge)
                cross_points.append(next_cp)
                if dfs_contain(goal, edges, cross_points):
                    break
                e = edges.pop()
                DP[e] = False
                cross_points.pop()
        else:
            return False
        return True
            
    from sys import stdin
    file_input = stdin.radlines()
    
    from itertools import combinations
    
    while True:
        n = int(lines[0])
        if n == 0:
            break
        
        edges = enumerate(map(string_to_complex, lines[1:1+n]))
        adj_edge = [[] for i in range(n)]
        
        for e1, e2 in combinations(edges, 2):
            n1, t1 = e1
            n2, t2 = e2
            cp = cross_point(*t1, *t2)
            if cp:
                adj_edge[n1].append((n2, cp))
                adj_edge[n2].append((n1, cp))
        
        flag = True
        while flag:
            for i, ae in enumerate(adj_edge):
                if len(ae) == 1:
                    ne, cp = ae.pop()
                    adj_edge[ne].remove((i, cp))
                    break
            else:
                flag = False
        
        unchecked = [True] * n
        
        for e in range(n):
            unchecked[e] = False
            DP = [True] * n
            if dfs_contain(e, [e], []):
                print('yes')
                break
        else:
            print('no')
        
        del lines[:1+n]

solve()

Submission status: Runtime Error

Solution code:
def string_to_complex(s):
    a, b, c, d = map(int, s.split())
    return (a + b * 1j, c + d * 1j)

def dot(c1, c2):
    return c1.real * c2.real + c1.imag * c2.imag

def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def cross_point(p1, p2, p3, p4):
    crs1 = cross(p2 - p1, p3 - p1)
    crs2 = cross(p2 - p1, p4 - p1)
    if crs1 == 0 and crs2 == 0:
        if p1 == p3 or p1 == p4:
            return p1
        elif p2 == p3 or p2 == p4:
            return p2
        else:
            return None
    crs3 = cross(p4 - p3, p1 - p3)
    crs4 = cross(p4 - p3, p2 - p3)
    if crs1 * crs2 <= 0 and crs3 * crs4 <= 0:
        base = p4 - p3
        hypo1 = p1 - p3
        hypo2 = p2 - p3
        d1 = abs(cross(base, hypo1)) / abs(base)
        d2 = abs(cross(base, hypo2)) / abs(base)
        return p1 + d1 / (d1 + d2) * (p2 - p1)
    else:
        return None

def contain(polygon):
    flag = False
    for a, b in zip(polygon[0:], polygon[1:] + [polygon[0]]):
        if a.imag > b.imag:
            a, b = b, a
        if a.imag <= 0 and b.imag > 0 and cross(a, b) > 0:
            flag = not flag
    return flag

def solve():
    def dfs_contain(goal, edges, cross_points):
        cur_edge = edges[-1]
        for next_edge, next_cp in adj_edge[cur_edge]:
            if next_edge == goal:
                if contain(cross_points + [next_cp]):
                    break
            elif next_edge not in edges and unchecked[next_edge] and DP[next_edge]:
                edges.append(next_edge)
                cross_points.append(next_cp)
                if dfs_contain(goal, edges, cross_points):
                    break
                e = edges.pop()
                DP[e] = False
                cross_points.pop()
        else:
            return False
        return True
            
    from sys import stdin
    file_input = stdin.readlines()
    
    from itertools import combinations
    
    while True:
        n = int(lines[0])
        if n == 0:
            break
        
        edges = enumerate(map(string_to_complex, lines[1:1+n]))
        adj_edge = [[] for i in range(n)]
        
        for e1, e2 in combinations(edges, 2):
            n1, t1 = e1
            n2, t2 = e2
            cp = cross_point(*t1, *t2)
            if cp:
                adj_edge[n1].append((n2, cp))
                adj_edge[n2].append((n1, cp))
        
        flag = True
        while flag:
            for i, ae in enumerate(adj_edge):
                if len(ae) == 1:
                    ne, cp = ae.pop()
                    adj_edge[ne].remove((i, cp))
                    break
            else:
                flag = False
        
        unchecked = [True] * n
        
        for e in range(n):
            unchecked[e] = False
            DP = [True] * n
            if dfs_contain(e, [e], []):
                print('yes')
                break
        else:
            print('no')
        
        del lines[:1+n]

solve()