Ssyrovatkin/task1 — различия между версиями

places_coords = []
roads = []
 
def orientation(p, q, r):
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
 
    return val > 0
 
def cross(a, b):
    """check if crosses p1q1 and p2q2"""
    p1, q1, p2, q2 = places_coords[a[0]], places_coords[a[1]], places_coords[b[0]], places_coords[b[1]]
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)
 
    # common case
    if o1 != o2 and o3 != o4:
        return True
 
    # don't cross
    return False
 
def dfs(root):
    current_tour = []
    u = root
    while True:
        current_tour.append(u)
        v = None
        for r in roads:
            if u not in r:
                continue
            curr = list(set(r) - set([u]))[0]
 
            if curr in current_tour:
                continue
            crossing = False
            for i in range(len(current_tour)-1):
                if cross((current_tour[i], current_tour[i+1]), r):
                    crossing = True
                    break
            if crossing: 
                continue
            else:
                v = curr
                break
 
        if v is None:
            break
        u = v
        roads.remove(r)
 
    return current_tour
 
# read N and coords of places
N = int(input())
 
for n in range(N):
    x, y = [int(i) for i in input().split(' ')]
    places_coords.append([n, x, y])
 
# adding roads in format: [(i1, j1), ...]
input_roads = []
for r in range(N):
    input_roads.append(input())
for i in range(N):
    for j in range(i+1, N):
        if input_roads[i][j] == 'Y':
            roads.append((i, j))
 
M = len(roads) # number of roads
 
tours = []
while roads:
    # find the first place in roads
    tours.append(dfs(roads[0][0]))
 
num_tours = len(tours)
print(num_tours)
for t in tours:
    print (len(t)-1, ' '.join(map(str,t)))