Counting Communication Groups
InterviewTime limit8sMemory limit256 MB
Count the connected groups of camps whose circular communication areas touch or overlap.
- Level
Easy3 of 10
- Topics
- Union-find, Geometry
- Solved
- No attempts yet
Problem
There are enemy camps on a two-dimensional plane. Each camp builds one communication tower, and the tower of camp takes every point within distance of its position as its communication area .
If the areas and touch or overlap, camp and camp communicate directly. Even without a direct link, two camps count as able to communicate when a chain of direct links connects them through other camps.
Camps that can communicate with each other move as one group. Count how many such groups there are.
Input
The first line contains the number of test cases . The test cases follow.
The first line of each test case contains the number of enemy camps (). Each of the next lines contains the coordinates , () of a camp and the radius () of its tower. All given numbers are integers.
Output
For each test case, print the number of groups of enemy camps on one line.