Martial's blog

By Martial, 4 years ago, In English,

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 »

Tags gcj
 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

By Martial, 9 years ago, In English,

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 = [0]*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 »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it