이상적인 도시(Ideal city) timer 1초 memory - MB

당대의 많은 이탈리아 과학자들과 예술가들처럼 다빈치는 도시 계획과 디자인에 대단한 관심이 있었다. 

다빈치는 편안하고, 공간을 넓고 합리적으로 사용하며, 

중세 시대 도시의 좁고 답답함과는 거리가 먼 이상적인 도시를 디자인할 계획을 가지고 있었다.

각 셀은 좌표들의 쌍 (행, 열)로 나타낸다. (i, j) 셀이 주어지면, 인접한 셀들은 (i-1, j), (i+1, j), (i, j-1) 그리고 (i, j+1) 이다. 

그리드 위에 놓여질 때, 각 블럭은 정확히 하나의 셀을 덮는다. 

블럭은 1 ≤ i, j ≤ 231 - 2 인 셀 (i, j) 에만 놓을 수 있다.

셀들 위에 놓여진 블럭들을 나타낼 때, 셀들의 좌표를 사용할 것이다. 

두 블럭이 서로 인접한 셀들에 놓여지면 두 블럭은 인접했다고 말한다. 

이상적인 도시에서 모든 블럭들은 도시안에 구멍이 없도록 연결된다. 

다시 말해서, 셀들은 아래의 조건들을 만족해야만 한다.

  * 임의의 두 비어 있는 셀들에 대해서, 

    인접한 비어 있는 셀들로만 이동하는 방법으로 한 셀에서 다른 셀에 도달할 수 있는 경로가 적어도 하나 이상 존재한다.

  * 임의의 두 비어있지 않은 셀들에 대해서, 

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

처음 두 개는 첫번째 조건을 만족하지 않고, 

세 번째 그림은 두번째 조건을 만족하지 않고, 

네번째 그림은 두 조건 모두를 만족하지 않는다.

비어있는 셀들로는 이동할 수 없다. V0 , V1 , …, Vn-1 을 그리드 위에 놓여 있는 N개 블럭들의 좌표라고 하자. 

좌표 Vi 와 Vj 를 가진 임의의 서로 다른 두 블럭들에 대해서, 

그들간의 거리 d(Vi, Vj)는 이 블럭들 중 하나에서 다른 곳으로 가는데 요구되는 걸음들의 최소수로 정의된다.

그리고 V10 = (5, 6) 를 가지는 N = 11 개의 블럭들로 이루어진 이상적인 도시를 나타낸다. 

그러면, d(V1 , V3 ) = 1, d(V1 , V8 ) = 6, d(V6 , V10 ) = 2, 그리고 d(V9 ,V10) = 4 이다.

정확히 말하면, 프로그램은 다음의 합을 계산해야 한다.

구체적으로, 도시를 나타내는 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 으로 나눈 나머지로 계산한다.

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