이상적인 도시

첫째 줄에 N이 주어진다. 다음 줄부터 N개 줄에는 블록의 좌표 X[i]와 Y[i]가 주어진다.

모든 가능한 i < j인 두 블록 쌍 vi와 vj에 대한 거리들의 합을 1,000,000,000 으로 나눈 나머지를 출력한다.

당대의 많은 이탈리아 과학자들과 예술가들처럼 다빈치는 도시 계획과 디자인에 대단한 관심이 있었다. 다빈치는 편안하고, 공간을 넓고 합리적으로 사용하며, 중세 시대 도시의 좁고 답답함과는 거리가 먼 이상적인 도시를 디자인할 계획을 가지고 있었다

무한 개 네모 셀들의 격자 위에 N 개의 블록들을 놓아서 도시를 만든다. 각 셀은 좌표들의 쌍 (행, 열)로 나타낸다. (i, j) 셀이 주어지면, 인접한 셀들은 (i-1, j), (i+1, j), (i, j-1) 그리고 (i, j+1) 이다. 그리드 위에 놓여질 때, 각 블록은 정확히 하나의 셀을 덮는다. 블록은 1 ≤ i, j ≤ 231- 2 인 셀 (i, j) 에만 놓을 수 있다. 셀들 위에 놓여진 블록들을 나타낼 때, 셀들의 좌표를 사용할 것이다. 두 블록이 서로 인접한 셀들에 놓여지면 두 블록은 인접했다고 말한다. 이상적인 도시에서 모든 블록들은 도시안에 구멍이 없도록 연결된다. 다시 말해서, 셀들은 아래의 조건들을 만족해야만 한다.

1. 임의의 두 비어 있는 셀들에 대해서, 인접한 비어 있는 셀들로만 이동하는 방법으로 한 셀에서 다른 셀에 도달할 수 있는 경로가 적어도 하나 이상 존재한다.
2. 임의의 두 비어있지 않은 셀들에 대해서, 인접한 비어있지 않은 셀들로만 이동하는 방법으로 한 셀에서 다른 셀에 도달할 수 있는 경로가 적어도 하나 이상 존재한다.

아래 그림 모두는 이상적인 도시가 아니다. 처음 두 개는 첫 번째 조건을 만족하지 않고, 세 번째 그림은 두 번째 조건을 만족하지 않고, 네 번째 그림은 두 조건 모두를 만족하지 않는다.

도시 안을 이동할 때, 걸음은 한 블록에서 인접한 블록으로 이동하는 것을 말한다. 비어있는 셀들로는 이동할 수 없다. v0, v1, …, vN-1 을 그리드 위에 놓여 있는 N 개 블록들의 좌표라고 하자. 좌표 vi 와 vj 를 가진 임의의 서로 다른 두 블록들에 대해서, 그들간의 거리 d(vi, vj)는 이 블록들 중 하나에서 다른 곳으로 가는데 요구되는 걸음들의 최소 수로 정의된다.

아래 그림은 좌표 v0 = (2, 5), v1 = (2, 6), v2 = (3, 3), v3 = (3, 6), v4 = (4, 3), v5 = (4, 4), v6 = (4, 5), v7 = (4, 6), v8 = (5, 3), v9 = (5, 4), 그리고 v10 = (5, 6) 를 가지는 N = 11 개의 블록들로 이루어진 이상적인 도시를 나타낸다. 그러면, d(v1, v3) = 1, d(v1, v8) = 6, d(v6, v10) = 2, 그리고 d(v9, v10) = 4 이다.

당신은 모든 가능한 i < j 인 두 블록 쌍 vi와 vj에 대한 거리들의 합을 계산하는 프로그램을 작성해야 한다. 정확히 말하면, 프로그램은 다음의 합을 계산해야 한다.

∑d(vi, vj), 단, 0 ≤ i < j ≤ N - 1

구체적으로, 도시를 나타내는 N 과 두 배열 X 와 Y 가 주어 질때, 위 공식을 계산하는 함수 DistanceSum(N, X, Y) 를 구현해야 한다. 배열 X 와 Y 는 크기 N 이고, 0 ≤ i ≤ N - 1 에 대해서, 블록 i 는 좌표 (X[i], Y[i])를 가지고 1 ≤ X[i], Y[i] ≤ 231- 2 이다. 결과가 32비트를 사용해서 표현하기에 너무 클 수 있기 때문에 결과를 1,000,000,000 으로 나눈 나머지로 계산한다.

위의 예제에서 11 × 10 / 2 = 55 개의 블록 쌍이 존재한다. 모든 쌍 간의 거리들의 합은 174 이다