Editing 2016 Dec Gold Problem 1 Moocast (section)

=== Python ===
<pre>
from collections import defaultdict

class Cow:
    def __init__(self, i, x, y):
        self.i = i
        self.x = x
        self.y = y

def dfs(graph, visited, node, val):
    if visited[node]:
        return
    visited[node] = True
    for edge in graph[node]:
        if visited[edge[0]]:
            continue
        if edge[1] <= val:
            dfs(graph, visited, edge[0], val)

def reach(graph, total, val):
    visited = [False] * total
    dfs(graph, visited, 0, val)
    return sum(visited) >= total

def main():
    with open('moocast.in', 'r') as fin:
        n = int(fin.readline().strip())
        cows = [Cow(i, *map(int, line.split())) for i, line in enumerate(fin)]

    min_distance = 625000000 * 2
    max_distance = 0
    graph = defaultdict(list)

    for cow in cows:
        for cow1 in cows:
            if cow.i == cow1.i:
                continue
            d = (cow1.x - cow.x)**2 + (cow1.y - cow.y)**2
            min_distance = min(d, min_distance)
            max_distance = max(d, max_distance)
            graph[cow.i].append((cow1.i, d))

    while min_distance < max_distance:
        mid = (min_distance + max_distance) // 2

        if reach(graph, n, mid):
            max_distance = mid
        else:
            min_distance = mid + 1

    with open('moocast.out', 'w') as fout:
        fout.write(str(max_distance) + '\n')

if __name__ == "__main__":
    main()

</pre>