만드는 중입니다

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

통신 그룹의 개수

면접 대비

시간 제한8초메모리 제한256 MB

요약
통신 영역이 닿거나 겹치는 캠프를 한 그룹으로 묶을 때 전체 그룹 수를 셉니다.
난이도

쉬움10점 중 3점

유형
유니온 파인드, 기하
정답자
아직 제출이 없습니다

문제

2차원 평면 위 NN곳에 적군 진영이 있다. 각 진영은 통신탑을 하나씩 세우고, ii번째 진영의 통신탑은 세워진 위치에서 거리 RiR_i 이내인 모든 지점을 통신영역 AiA_i로 삼는다.

두 통신영역 AiA_i와 AjA_j가 닿거나 겹치는 부분이 있으면 진영 ii와 진영 jj는 직접 통신할 수 있다. 직접 통신하지 못하더라도 중간에 다른 진영을 몇 번 거쳐 이어지면 두 진영은 서로 통신할 수 있는 것으로 본다.

서로 통신할 수 있는 진영끼리는 하나의 그룹처럼 움직인다. 이런 그룹이 몇 개인지 세어라.

입력

첫째 줄에 테스트 케이스의 수 TT가 주어진다. 이어서 TT개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 적군 진영의 수 NN (1≤N≤30001 \le N \le 3000)이 주어진다. 다음 NN개의 줄에는 진영의 좌표 xx, yy (0≤x,y≤50000 \le x, y \le 5000)와 통신탑의 반지름 RR (0≤R≤50000 \le R \le 5000)이 주어진다. 주어지는 수는 모두 정수이다.

출력

각 테스트 케이스마다 적군 진영의 그룹 개수를 한 줄에 출력한다.

예제3

  1. 예제 1

    입력
    2
    2
    0 0 1
    1 0 1
    3
    0 0 1
    2 0 1
    10 0 5
    
    예상 출력
    1
    2
    
  2. 예제 2

    입력
    1
    1
    2500 2500 0
    
    예상 출력
    1
    
  3. 예제 3

    입력
    3
    2
    0 0 3
    7 0 4
    2
    0 0 3
    8 0 4
    2
    0 0 0
    0 0 0
    
    예상 출력
    1
    2
    1