만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

동심원

시간 제한2초메모리 제한1024 MB

요약
중심이 서로 다른 두 동심원 묶음이 주어질 때, 모든 원이 만드는 유계 영역의 개수를 구합니다.
난이도

보통10점 중 7점

유형
수학, 기하, 이분 탐색
정답자
아직 제출이 없습니다

문제

외계 침략자들이 다시 지구로 원정대를 보냈다. 주민들을 겁주기 위해 들판에 원을 그리기로 했다.

침략자들은 들판의 점 (x1,y1)(x_1, y_1)을 중심으로 반지름이 a1,a2,…,ana_1, a_2, \dots, a_n인 원 nn개를 그렸다. 이어서 다른 점 (x2,y2)(x_2, y_2)를 중심으로 반지름이 b1,b2,…,bmb_1, b_2, \dots, b_m인 원 mm개를 그렸다.

지구 주민들은 외계인을 크게 경계하지는 않지만, 혹시 몰라 침략자들이 그린 원의 선으로 둘러싸인 영역이 들판에 몇 개 생겼는지 알고 싶어 한다.

입력

첫 번째 줄에 정수 x1x_1, y1y_1이 주어진다 (−109≤x1,y1≤109-10^9 \le x_1, y_1 \le 10^9).

두 번째 줄에 정수 nn (1≤n≤100 0001 \le n \le 100\,000)이 주어진다. 그 뒤에 엄격하게 증가하는 순서로 정수 a1,a2,…,ana_1, a_2, \dots, a_n이 주어진다 (1≤ai≤2⋅1091 \le a_i \le 2 \cdot 10^9).

세 번째 줄에 정수 x2x_2, y2y_2가 주어진다 (−109≤x2,y2≤109-10^9 \le x_2, y_2 \le 10^9). 두 점 (x1,y1)(x_1, y_1)과 (x2,y2)(x_2, y_2)는 서로 같지 않다.

네 번째 줄에 정수 mm (1≤m≤100 0001 \le m \le 100\,000)이 주어진다. 그 뒤에 엄격하게 증가하는 순서로 정수 b1,b2,…,bmb_1, b_2, \dots, b_m이 주어진다 (1≤bi≤2⋅1091 \le b_i \le 2 \cdot 10^9).

출력

원들이 만든 영역의 개수를 출력한다. 바깥 영역은 포함하지 않는다.

힌트

첫 번째 예시에서 영역은 다음과 같다.

예제3

  1. 예제 1

    입력
    3 8
    2 5 6
    9 13
    2 3 4
    
    예상 출력
    9
    
  2. 예제 2

    입력
    1 1
    1 1
    5 4
    2 4 6
    
    예상 출력
    3
    
  3. 예제 3

    입력
    -1000 2345
    1 1
    934 -1344
    4 4 5 6 10
    
    예상 출력
    5