blob: 198041462c4471e493a0545ec185745eb4b89f3a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
import fileinput
N = 1000 # Change to 10 for test case
with fileinput.input() as lines:
pts = [tuple(int(x) for x in line[:-1].split(',')) for line in lines]
r = range(len(pts))
def dist(p, q):
return (p[0]-q[0])**2 + (p[1]-q[1])**2 + (p[2]-q[2])**2
d = sorted([(dist(pts[i], pts[j]), i, j) for i in r for j in r if j > i])
rep = [i for i in r]
def findrep(i):
return i if rep[i] == i else findrep(rep[i])
def joinrep(i, j):
rep[findrep(i)] = findrep(j)
for i in range(N):
j, k = d[i][1], d[i][2]
if findrep(j) != findrep(k):
joinrep(j, k)
sizes = [[0, i] for i in r]
for i in r:
sizes[findrep(i)][0] += 1
sizes.sort()
print(sizes[-1][0] * sizes[-2][0] * sizes[-3][0])
|
