5813번 - 이상적인 도시 서브태스크

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

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

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

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

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

아래 그림은 좌표 v₀ = (2, 5), v₁ = (2, 6), v₂ = (3, 3), v₃ = (3, 6), v₄ = (4, 3), v₅ = (4, 4), v₆ = (4, 5), v₇ = (4, 6), v₈ = (5, 3), v₉ = (5, 4), 그리고 v₁₀ = (5, 6) 를 가지는 N = 11 개의 블록들로 이루어진 이상적인 도시를 나타낸다. 그러면, d(v₁, v₃) = 1, d(v₁, v₈) = 6, d(v₆, v₁₀) = 2, 그리고 d(v₉, v₁₀) = 4 이다.

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

∑d(v_i, v_j), 단, 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] ≤ 2³¹- 2 이다. 결과가 32비트를 사용해서 표현하기에 너무 클 수 있기 때문에 결과를 1,000,000,000 으로 나눈 나머지로 계산한다.

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

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

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

• N ≤ 200

• N ≤ 2 000

• N ≤ 100 000

더불어 다음 두 조건들이 만족된다.

• X[i] = X[j] 인 임의의 두 비어있지 않은 셀들이 주어질 때, 그들 사이의 모든 셀들 또한 비어있지 않다.
• Y[i] = Y[j] 인 임의의 두 비어있지 않은 셀들이 주어질 때, 그들 사이의 모든 셀들 또한 비어있지 않다.

• N ≤ 100 000