Ssyrovatkin/task1

• Codechef/TOURBUS

    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)))

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.