Cow Tours

cowtour

Algorithm

Run floodfill to find connected components, precompute distances between each pair of points with Floyd-Warshall, and then calculate the diameter of each component. Then we iterate through each pair of point between each pair of components:

for each component a:
    for each other component b:
        for each point i in a:
            get farthest point k from i in a
            for each point j in b:
                get farthest point l from j in b
                diameter = max(
                    diameter of a,
                    diameter of b,
                    distance between i and j + dist[i][k] + dist[j][l]
                )

Python

def setio(name):
    # Overwrites input/print functions to file io
    global input, print
    fIn = open(f"{name}.in", "r")
    fOut = open(f"{name}.out", "w")
    input = fIn.readline
    print = lambda i: fOut.write(str(i)+"\n")

def floydWarshall(adj, v):
    # Floyd-Warshall Algorithm
    dist = [[float("inf")] * v for _ in range(v)]
    for i in range(v):
        for x in adj[i]:
            weight = euclideanDist(pos[i], pos[x])
            dist[i][x] = weight
        dist[i][i] = 0
    for k in range(v):
        for i in range(v):
            for j in range(v):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

def floodFill(adj, v):
    # Floodfill Algorithm
    vis = [False] * v
    comp = []
    for i in range(v):
        curr = set()
        if not vis[i]:
            stack = [i]
            vis[i] = True
            while stack:
                x = stack.pop()
                curr.add(x)
                for y in adj[x]:
                    if not vis[y]:
                        vis[y] = True
                        stack.append(y)
            comp.append(curr)
    return comp

def euclideanDist(x, y):
    # Euclidean distance between two points
    return ((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2) ** 0.5

# Input handling
setio("cowtour")
n = int(input())
pos = []
for _ in range(n):
    pos.append(list(map(int, input().split())))
adj = [[] for _ in range(n)]
for i in range(n):
    line = input()
    for j in range(n):
        if line[j] == "1":
            adj[i].append(j)
            adj[j].append(i)

# Precompute distances between each pair of points
dist = floydWarshall(adj, n)

# Find connected components
comp = floodFill(adj, n)

# Find diameter of each component
diam = []
for component in comp:
    maxDist = 0
    for x in component:
        for y in component:
            maxDist = max(maxDist, dist[x][y])
    diam.append(maxDist)

opt = float("inf")
for a in range(len(comp)):
    for i in comp[a]:
        ik_dist = 0
        for k in comp[a]:
            ik_dist = max(ik_dist, dist[i][k])    
        for b in range(a + 1, len(comp)):
            for j in comp[b]:
                jl_dist = 0
                for l in comp[b]:
                    jl_dist = max(jl_dist, dist[j][l])
                opt = min(
                    opt,
                    max(
                        diam[a],
                        diam[b],
                        euclideanDist(pos[i], pos[j]) + ik_dist + jl_dist
                    )
                )
print(f"{opt:.6f}")