### Martial's blog

By Martial, 4 years ago, , For C large: "The smallest difference in angle between two points is approximately 1.25 * 10-13 radians." It looks like ( - n,  - n) ( - n + 1,  - n + 1) and (n, n - 1) form an optimal angle, but why ?

Here is a quick proof: minimizing the angle is equivalent to minimizing its sine. And then the area of a triangle with sides of length b and c is 2 * b * c * sin(A)

By Pick's Theorem: the smallest area of a triangle with integer coordinates is 1/2. It's the case when no points lie inside or on the edges. So, what remains is to take the two largest segments with no lattice points inside them.

Read more » By Martial, 9 years ago, , Hi I have this submission for problem D.  It doesn't pass the test, could anyone tell me why?  Thanks in advance.

n=int(input())
neighbors = [[] for i in range(n)]
for i in range(n-1):
a,b=map(int,raw_input().split())
a -= 1
b -= 1
neighbors[a].append(b)
neighbors[b].append(a)

def dfs(f,u):
visited[u]=True
father[u]=f
for v in neighbors[u]:
if not visited[v]:
dfs(u,v)

def f(u):
if dist[u]==-1:
res=0
for v in neighbors[u]:
if u==father[v]:
res = max(res,1+f(v))
dist[u]=res
return dist[u]

def g(u):
for v in neighbors[u]:
if u==father[v]:
dist_to_root[v] = 1+dist_to_root[u]
g(v)
return

res=0
if n>=4:
for root in range(n):
# direct the edges of the tree starting from the root.
if len(neighbors[root])<3:
visited = [False]*n
father = [-1]*n
dfs(-1,root)
# dist is the maximum distance to a leaf
dist = [-1]*n
f(root)
dist_to_root = [-1]*n
dist_to_root[root]=0
g(root)

score = *n
for u in range(n):
for v in neighbors[u]:
if u==father[v]:
score[u] += 1+dist[v]

for u in range(n):
on_path = [False]*n
w=u
while w!=-1:
on_path[w]=True
w=father[w]
for v in range(n):
if not on_path[v]:
res=max(res,dist_to_root[u]*score[v])
print res,

Read more » 