Ssyrovatkin/task1 — различия между версиями
Материал из DISCOPAL
Строка 72: | Строка 72: | ||
if input_roads[i][j] == 'Y': | if input_roads[i][j] == 'Y': | ||
roads.append((i, j)) | roads.append((i, j)) | ||
− | |||
− | |||
tours = [] | tours = [] | ||
Строка 87: | Строка 85: | ||
</source> | </source> | ||
+ | |||
+ | {{checkme|[[Участник:Ssyrovatkin|Ssyrovatkin]] 11:05, 26 сентября 2024 (UTC)}} |
Текущая версия на 11:05, 26 сентября 2024
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)) 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)))
Решено: Ssyrovatkin 11:05, 26 сентября 2024 (UTC)