IOI 2012 day2 1- 이상적인 도시(Ideal city) > 문제은행 : 정보올림피아드&알고리즘




2603 : 이상적인 도시(Ideal city)

제한시간
1000 ms   
메모리제한
0 MB   
해결횟수
12 회   
시도횟수
42 회   

문제

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

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

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

 

 

이상적인 도시
무한 개 네모 셀들의 격자 위에 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 이다.

 


입력형식

입력의 첫줄에 도시의 수 N(1≤N≤100,000)이 들어오고, 그 다음 줄부터 N줄에 걸쳐 좌표 x[i] y[i]가 공백으로 구분하여 들어온다.


출력형식

출력의 첫줄에 모든 쌍 간의 거리들의 합을 출력한다.


입력 예

11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6

출력 예

174


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP