Informatica Online Judge

  교준이의 심부름꾼, 민제의 고충 ("Circle" Ver.) [2305 / 0901]

Time Limit(Test case) : 6000(ms)
Number of users who solved : 1   Total Tried : 1


The Champion of this Problem (C++) : gs17068 - ms / 11225byte
My Best Submission (C++) : N/A

[35th 윤교준]

Background

민제는 지하철 하나 없는 대한민국의 유일한 도시 청주에서 살고 있다.
현재 3009년 5월, 교준이는 청주시장이다. 교준이는 낙후된 도시, 청주를 개발하려 한다.

2차원 평면인 청주에는 중심이 $(X_i, Y_i)$고 반지름이 $R_i$인 $N$개의 원이 존재한다.
$N$개의 원은 서로 교차하거나 접하지 않음이 보장된다.

청주에는 총 $M$채의 민제네 집이 있다. $i$번째 집의 위치는 $(A_i, B_i)$며, 이 집을 부수었을 때 교준이가 얻는 행복도는 $C_i$다.
집의 위치나 행복도는 서로 같을 수 있으나, 모든 $M$채의 집은 $N$개의 원 위에 존재하지 않음이 보장된다.

집을 부수었을 때 교준이가 얻는 행복도의 정의는 조금 특이하다.
어떤 집도 부숴지지 않았다면, 교준이는 0의 행복도를 얻는다.
만일 행복도 3인 집과 행복도 6인 집이 부수어졌다면, 교준이는 $3⊕6 = 5$의 행복도를 얻는다.
즉, 행복도가 $c_1$, $c_2$, ..., $c_k$인 집 $k$채가 부숴졌다면, 교준이는 총 $(c_1 ⊕ c_2 ⊕ ... ⊕ c_i)$의 행복도를 얻게 된다.
이 때 ⊕는 배타적 논리합을 나타내는 기호다.

민제네 집은 미관상으로 그리 좋지 못하다.
청주시장 교준이는, 청주를 현대도시로 발전시키기 위해서 민제네 집을 모조리 부수어버려야 한다고 생각한다.
또한 교준이는 매우 악랄하기 때문에, 민제보고 직접 민제네 집을 철거하라고 명령할 것이다.

만일 교준이가 민제에게 "$(x, y)$로 가서 거리 $L$ 이내에 있는 너네 집을 모두 부숴라."라고 명령하면, 민제는 $(x, y)$ 위치로 이동한 다음, 이 점으로부터 거리가 $L$ 이하인 모든 민제네 집을 직접 부순다.
이 때 두 점 간의 거리라 함은, 한 점에서 다른 점으로 이동하기 위해 지나야 하는 원의 최소 개수를 의미한다.
점 $(x, y)$가 $N$개의 원 위에 존재하지 않음은 항상 보장된다.

"민제네 집 철거 공사 계획"을 세우고 있던 교준이는 다음과 같은 궁금증이 생겼다:
"민제에게 "$(U_1, V_1)$로 가서 거리 $L_1$ 이내에 있는 너네 집을 모두 부숴라."라고 명령한 후,
다시 민제에게 "$(U_2, V_2)$로 가서 거리 $L_2$ 이내에 있는 너네 집을 모두 부숴라."라고 명령한 후,
...
다시 민제에게 "$(U_K, V_K)$로 가서 거리 $L_K$ 이내에 있는 너네 집을 모두 부숴라."라고 총 $K$차례 명령한다면,
내가 얻는 총 행복도는 얼마일까?""

교준이의 영원한 심부름꾼, 민제는 오늘도 교준이의 궁금증을 해결해주어야 한다.
허나 민제는 "1+9+10=19"라고 말할 정도로 수학을 못하는 바보다.
민제를 위하여 교준이의 질문에 답해주는 프로그램을 작성해보자!

Input

첫 번째 줄에는 청주의 원의 개수를 나타내는 자연수 $N$과 민제네 집의 수를 나타내는 자연수 $M$, 교준이의 궁금증 횟수를 나타내는 자연수 $Q$가 사이에 공백을 두고 주어진다.
두 번째 줄부터 $N$개의 줄에 걸쳐 $N$개의 원에 관한 정보가 주어진다.
$(i+1)$번째 줄에는 세 정수 $X_i$, $Y_i$, $R_i$가 사이에 공백을 두고 주어진다($1 ≤ i ≤ N$).
$(N+2)$번째 줄부터 $M$개의 줄에 걸쳐 $M$채의 민제네 집에 관한 정보가 주어진다.
$(N+i+1)$번째 줄에는 세 정수 $A_i$, $B_i$, $C_i$가 사이에 공백을 두고 주어진다($1 ≤ i ≤ M$).
$(N+M+2)$번째 줄부터 아래와 같은 형식으로 $Q$개의 교준이의 궁금증에 관한 정보가 주어진다.
하나의 궁금증은 여러 줄에 걸쳐 표현되며, 아래와 같은 형식을 갖는다.
첫 번째 줄에는 민제에게 명령하는 총 횟수를 나타내는 자연수 $K$가 주어진다.
두 번째 줄부터 $K$개의 줄에 걸쳐 $K$번의 명령에 관한 정보가 주어진다.
$(i+1)$번째 줄에는 세 정수 $U_i$, $V_i$, $L_i$가 사이에 공백을 두고 주어진다($1 ≤ i ≤ K$).

[입력값의 제약조건]
모든 입력 데이터는 아래의 조건을 모두 만족한다.
$1 ≤ N ≤ 250,000$
$1 ≤ M ≤ 250,000$
$1 ≤ Q ≤ 250,000$
$Q$개의 궁금증의 $K$들의 합은 250,000을 넘지 않는다.
$-10^9 ≤ X_i ≤ 10^9$ ($1 ≤ i ≤ N$)
$-10^9 ≤ Y_i ≤ 10^9$ ($1 ≤ i ≤ N$)
$1 ≤ R_i ≤ 10^9$ ($1 ≤ i ≤ N$)
$i$번째 원과 $j$번째 원은 서로 교차하거나 접하지 않는다($1 ≤ i < j ≤ N$).
$-10^9 ≤ A_i ≤ 10^9$ ($1 ≤ i ≤ M$)
$-10^9 ≤ B_i ≤ 10^9$ ($1 ≤ i ≤ M$)
$0 ≤ C_i < 2^{31}$ ($1 ≤ i ≤ M$)
$i$번째 원 위에 점 $(A_j, B_j)$가 존재하지 않는다($1 ≤ i ≤ N$, $1 ≤ j ≤ M$).
각 궁금증에 대하여, $-10^9 ≤ U_i ≤ 10^9$ ($1 ≤ i ≤ K$)
각 궁금증에 대하여, $-10^9 ≤ V_i ≤ 10^9$ ($1 ≤ i ≤ K$)
각 궁금증에 대하여, $0 ≤ L_i ≤ N$ ($1 ≤ i ≤ K$)
각 궁금증에 대하여, $i$번째 원 위에 점 $(U_j, V_j)$가 존재하지 않는다($1 ≤ i ≤ N$, $1 ≤ j ≤ K$).

Output

첫 번째 줄부터 $Q$개의 줄에 걸쳐 교준이가 얻는 행복도를 차례대로 출력한다.

IO Example

IO Example
입력
15 10 7
2 6 1
4 8 1
5 3 1
5 10 1
6 4 3
7 5 1
8 9 2
10 6 1
6 6 6
12 10 1
13 5 1
14 2 2
15 9 1
17 7 1
16 8 3
1 9 9
3 5 8
4 6 10
4 8 3
6 8 1
6 11 4
7 5 6
13 1 5
15 7 15
15 11 11
1
9 7 0
1
12 4 1
1
17 7 0
1
17 9 1
2
1 2 0
15 5 1
2
9 7 1
17 9 0
3
6 4 0
8 3 0
5 3 1

출력
4
5
0
4
5
9
10

보충 설명









Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]