output_description: Print the number of triples that satisfy the condition.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      H W
      s_{11}...s_{1W}
      :
      s_{H1}...s_{HW}
attempt: import itertools
  import sys
  
  H, W = [int(i) for i in input().split(" ")]
  
  cross = [[0] * (H + W - 1) for _ in range(H + W - 1)]
  for i, line in enumerate(sys.stdin):
      for j, c in enumerate(line.strip()):
          if c == "#":
              cross[i + j][i - j + W - 1] = 1
  
  across = [[0] + list(itertools.accumulate(xs)) for xs in cross]
  r_cross = [[xs[i] for xs in cross] for i in range(H + W - 1)]
  across2 = [[0] + list(itertools.accumulate(xs)) for xs in r_cross]
  
  r = 0
  for i in range(H + W - 1):
      for j in range(H + W - 1):
          if cross[i][j] != 1:
              continue
          for k in range(j + 1, H + W - 1):
              if cross[i][k] == 1:
                  if i - (k - j) >= 0:
                      r += across[i - (k - j)][k + 1] - across[i - (k - j)][j]
                  if i + (k - j) < H + W - 1:
                      r += across[i + (k - j)][k + 1] - across[i + (k - j)][j]
  
  print(r)
  
problem_description: Statement
  
  There are some coins in the xy-plane. The positions of the coins are
  represented by a grid of characters with H rows and W columns. If the
  character at the i-th row and j-th column, s_{ij}, is `#`, there is one coin
  at point (i,j); if that character is `.`, there is no coin at point (i,j).
  There are no other coins in the xy-plane.
  
  There is no coin at point (x,y) where 1\leq i\leq H,1\leq j\leq W does not
  hold. There is also no coin at point (x,y) where x or y (or both) is not an
  integer. Additionally, two or more coins never exist at the same point.
  
  Find the number of triples of different coins that satisfy the following
  condition:
  
    * Choosing any two of the three coins would result in the same Manhattan distance between the points where they exist.
  
  Here, the Manhattan distance between points (x,y) and (x',y') is
  |x-x'|+|y-y'|. Two triples are considered the same if the only difference
  between them is the order of the coins.
samples: [{"input": "5 4\n    #.##\n    .##.\n    #...\n    ..##\n    ...#", "output": "3\n    \n\n((1,1),(1,3),(2,2)),((1,1),(2,2),(3,1)) and ((1,3),(3,1),(4,4)) satisfy the\ncondition.\n\n* * *"}, {"input": "13 27\n    ......#.........#.......#..\n    #############...#.....###..\n    ..............#####...##...\n    ...#######......#...#######\n    ...#.....#.....###...#...#.\n    ...#######....#.#.#.#.###.#\n    ..............#.#.#...#.#..\n    #############.#.#.#...###..\n    #...........#...#...#######\n    #..#######..#...#...#.....#\n    #..#.....#..#...#...#.###.#\n    #..#######..#...#...#.#.#.#\n    #..........##...#...#.#####", "output": "870"}]