Ssyrovatkin/task1 — различия между версиями
Материал из DISCOPAL
Строка 2: | Строка 2: | ||
<source lang="python"> | <source lang="python"> | ||
+ | |||
places_coords = [] | places_coords = [] | ||
roads = [] | roads = [] | ||
Строка 41: | Строка 42: | ||
for i in range(len(current_tour)-1): | for i in range(len(current_tour)-1): | ||
if cross((current_tour[i], current_tour[i+1]), r): | if cross((current_tour[i], current_tour[i+1]), r): | ||
− | + | crossing = True | |
− | + | break | |
if crossing: | if crossing: | ||
continue | continue | ||
Строка 83: | Строка 84: | ||
for t in tours: | for t in tours: | ||
print (len(t)-1, ' '.join(map(str,t))) | print (len(t)-1, ' '.join(map(str,t))) | ||
+ | |||
+ | |||
</source> | </source> |
Версия 11:03, 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)) 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)))