Ssyrovatkin/task1 — различия между версиями
Материал из DISCOPAL
(Новая страница: «*Codechef/TOURBUS <source lang="python"> places_coords = [] roads = [] def orientation(p, q, r): val = (q[1] - p[1]) * (r[0] - q[0]) - (…») |
|||
Строка 2: | Строка 2: | ||
<source lang="python"> | <source lang="python"> | ||
− | + | 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 | 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))) | ||
</source> | </source> |
Версия 10:53, 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)))