시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 16 9 9 64.286%

문제

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

무한 개 네모 셀들의 격자 위에 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 이다

입력

첫째 줄에 N이 주어진다. 다음 줄부터 N개 줄에는 블럭의 좌표 X[i]와 Y[i]가 주어진다. (N ≤ 100,000)

출력

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

예제 입력

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

예제 출력

174

힌트

출처

Olympiad > International Olympiad in Informatics > IOI 2012 4번

  • 문제의 오타를 찾은 사람: suhgyuho