문제 설명
우주세기(Universal Century) 923년, 우리 은하의 자원이 고갈되어 인류는 새로운 은하를 개척하려고 합니다.
인류는 다른 은하의 행성계에 정착할 수 있는 우주선 "방주"를 만들어냈습니다.
그러나 행성계에 정착하면 "방주"를 다시는 사용할 수도, 새로 만들 수도 없습니다.
대신 행성계를 개척하면 행성계의 자원을 바탕으로 우주선을 만들어 근처 행성계를 추가로 개척할 수 있습니다.
임의의 은하에 대한 행성계의 정보가 다음과 같이 주어집니다. (우주의 공간 좌표는 3차원이나, 편의상 2차원으로 제공합니다.)
그리고 행성계 B와 C를 개척하여 만든 우주선으로 탐사할 수 있는 범위 안에 다른 행성계의 좌표가 있다면 그 행성계도 개척할 수 있습니다.
그러나 행성계 A에서 개척한 자원은 그 행성계의 범위에서만 사용할 수 있습니다. 따라서 행성계 A의 자원을 행성계 B나 C에서는 사용할 수 없습니다.
은하에 대한 행성계의 정보가 주어졌을 때, 개척할 수 있는 행성계의 최대 수를 구해주세요.
행성계 2를 먼저 개척할 경우 행성계 1의 중심 좌표까지는 탐험할 수 없으므로 개척할 수 있는 행성계는 총 1개입니다.
따라서 이 은하에서 개척할 수 있는 행성계의 최대 수는 1입니다.
행성계 2를 먼저 개척할 경우 행성계 1의 중심 좌표까지 탐험할 수 없으므로 개척할 수 있는 행성계는 총 1개입니다.
따라서 이 은하에서 개척할 수 있는 행성계의 최대 수는 2입니다.
그리고 행성계 2를 개척하면 행성계 3과 5의 중심 좌표까지 탐험하여 개척할 수 있습니다.
따라서 총 5개의 행성계를 개척할 수 있습니다.
행성계 2를 먼저 개척하면 행성계 3과 5의 중심 좌표까지 탐험하여 개척할 수 있습니다.
그러나 행성계 1과 4의 경우 중심 좌표까지 탐험할 수 없으므로 개척할 수 없습니다.
따라서 총 3개의 행성계를 개척할 수 있습니다.
행성계 3을 먼저 개척하면 행성계 2의 중심 좌표까지 탐험하여 개척할 수 있습니다.
그리고 행성계 2를 개척하면 행성계 5의 중심 좌표까지 탐험하여 개척할 수 있습니다.
그러나 행성계 1과 4의 경우 중심 좌표까지 탐험할 수 없으므로 개척할 수 없습니다.
따라서 총 3개의 행성계를 개척할 수 있습니다.
행성계 4 또는 5를 먼저 개척하면 탐험할 수 있는 다른 행성계는 없습니다.
따라서 이 경우 총 1개의 행성계만 개척할 수 있습니다.
정리하면 이 은하에서 개척할 수 있는 행성계의 최대 수는 5입니다.
인류는 다른 은하의 행성계에 정착할 수 있는 우주선 "방주"를 만들어냈습니다.
그러나 행성계에 정착하면 "방주"를 다시는 사용할 수도, 새로 만들 수도 없습니다.
대신 행성계를 개척하면 행성계의 자원을 바탕으로 우주선을 만들어 근처 행성계를 추가로 개척할 수 있습니다.
임의의 은하에 대한 행성계의 정보가 다음과 같이 주어집니다. (우주의 공간 좌표는 3차원이나, 편의상 2차원으로 제공합니다.)
- 은하에서 개척할 수 있는 행성계의 좌표 x, y
- 행성계 위치를 중심으로 행성계를 개척하여 만든 우주선으로 탐험할 수 있는 범위인 반지름 r
그리고 행성계 B와 C를 개척하여 만든 우주선으로 탐사할 수 있는 범위 안에 다른 행성계의 좌표가 있다면 그 행성계도 개척할 수 있습니다.
그러나 행성계 A에서 개척한 자원은 그 행성계의 범위에서만 사용할 수 있습니다. 따라서 행성계 A의 자원을 행성계 B나 C에서는 사용할 수 없습니다.
은하에 대한 행성계의 정보가 주어졌을 때, 개척할 수 있는 행성계의 최대 수를 구해주세요.
예시 1
<그림> 은하 지도 (점: 행성계 위치, 영역: 행성계를 개척하여 만든 우주선으로 탐험할 수 있는 범위)
예를 들어 어떤 은하에 대한 행성계의 정보가 다음과 같이 주어져있다고 가정해 봅시다.
- 행성계 1: (x1, y1, r1) = (2, 4, 3)
- 행성계 2: (x2, y2, r2) = (5, 2, 2)
행성계 2를 먼저 개척할 경우 행성계 1의 중심 좌표까지는 탐험할 수 없으므로 개척할 수 있는 행성계는 총 1개입니다.
따라서 이 은하에서 개척할 수 있는 행성계의 최대 수는 1입니다.
예시 2
<그림> 은하 지도 (점: 행성계 위치, 영역: 행성계를 개척하여 만든 우주선으로 탐험할 수 있는 범위)
예를 들어 어떤 은하에 대한 행성계의 정보가 다음과 같이 주어져있다고 가정해 봅시다.
- 행성계 1: (x1, y1, r1) = (2, 4, 3)
- 행성계 2: (x2, y2, r2) = (5, 4, 2)
행성계 2를 먼저 개척할 경우 행성계 1의 중심 좌표까지 탐험할 수 없으므로 개척할 수 있는 행성계는 총 1개입니다.
따라서 이 은하에서 개척할 수 있는 행성계의 최대 수는 2입니다.
예시 3
<그림> 은하 지도 (점: 행성계 위치, 영역: 행성계를 개척하여 만든 우주선으로 탐험할 수 있는 범위)
예를 들어 어떤 은하에 대한 행성계의 정보가 다음과 같이 주어져있다고 가정해 봅시다.
- 행성계 1: (x1, y1, r1) = (2, 2, 3)
- 행성계 2: (x2, y2, r2) = (5, 2, 2)
- 행성계 3: (x3, y3, r3) = (5, 3, 1)
- 행성계 4: (x4, y4, r4) = (1, 1, 1)
- 행성계 5: (x5, y5, r5) = (6, 1, 1)
그리고 행성계 2를 개척하면 행성계 3과 5의 중심 좌표까지 탐험하여 개척할 수 있습니다.
따라서 총 5개의 행성계를 개척할 수 있습니다.
행성계 2를 먼저 개척하면 행성계 3과 5의 중심 좌표까지 탐험하여 개척할 수 있습니다.
그러나 행성계 1과 4의 경우 중심 좌표까지 탐험할 수 없으므로 개척할 수 없습니다.
따라서 총 3개의 행성계를 개척할 수 있습니다.
행성계 3을 먼저 개척하면 행성계 2의 중심 좌표까지 탐험하여 개척할 수 있습니다.
그리고 행성계 2를 개척하면 행성계 5의 중심 좌표까지 탐험하여 개척할 수 있습니다.
그러나 행성계 1과 4의 경우 중심 좌표까지 탐험할 수 없으므로 개척할 수 없습니다.
따라서 총 3개의 행성계를 개척할 수 있습니다.
행성계 4 또는 5를 먼저 개척하면 탐험할 수 있는 다른 행성계는 없습니다.
따라서 이 경우 총 1개의 행성계만 개척할 수 있습니다.
정리하면 이 은하에서 개척할 수 있는 행성계의 최대 수는 5입니다.
입력 설명
첫 줄에는 테스트케이스 T(1 ≤ T ≤ 102)가 주어집니다.
각 테스트케이스의 첫 줄에는 은하의 행성계 수 P(1 ≤ P ≤ 102)가 주어집니다.
그다음 P줄에 각 행성계의 위치 x(1 ≤ x ≤ 105), y(1 ≤ y ≤ 105), 행성계를 개척했을 때 만든 우주선으로 개척할 수 있는 범위 r(1 ≤ r ≤ 105)이 주어집니다.
각 테스트케이스의 첫 줄에는 은하의 행성계 수 P(1 ≤ P ≤ 102)가 주어집니다.
그다음 P줄에 각 행성계의 위치 x(1 ≤ x ≤ 105), y(1 ≤ y ≤ 105), 행성계를 개척했을 때 만든 우주선으로 개척할 수 있는 범위 r(1 ≤ r ≤ 105)이 주어집니다.
출력 설명
주어진 각각의 은하에 대한 정보에서 개척할 수 있는 행성계의 최대 수를 구하여 출력합니다.
입력 예시 Copy
3
2
2 4 3
5 2 2
2
2 4 3
5 4 2
5
2 2 3
5 2 2
5 3 1
1 1 1
6 1 1
출력 예시 Copy
1
2
5
도움
좌표가 (x1, y1), 반지름이 r1인 임의의 원 A와, 좌표가 (x2, y2)인 임의의 점 B가 주어졌을 때,
A의 중심 좌표와 점 B의 좌표 사이의 거리가 반지름 r1보다 작거나 같으면 원 A에 점 B가 포함됩니다.
따라서 아래와 같은 수식이 참인지 판별하여 임의의 행성계에서 다른 행성계를 탐험할 수 있는지를 판단할 수 있습니다.
A의 중심 좌표와 점 B의 좌표 사이의 거리가 반지름 r1보다 작거나 같으면 원 A에 점 B가 포함됩니다.
따라서 아래와 같은 수식이 참인지 판별하여 임의의 행성계에서 다른 행성계를 탐험할 수 있는지를 판단할 수 있습니다.