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

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

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

이상적인 도시

무한 개 네모 셀들의 격자 위에 N 개의 블럭들을 놓아서 도시를 만든다.

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

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

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

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

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

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

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

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

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

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

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

예제 1

아래 그림 모두는 이상적인 도시가 아니다.

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

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

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

거리

도시 안을 이동할 때, 걸음은 한 블럭에서 인접한 블럭으로 이동하는 것을 말한다.

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

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

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

예제 2

아래 그림은 좌표 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 인 두 블럭 쌍 v 와 v 에 대한 거리들의 합을 계산하는 프로그램을 작성해야 한다.

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

Σ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 으로 나눈 나머지로 계산한다.

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

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

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