UVa 10301

From Algorithmist
Jump to: navigation, search

10301 - Rings and Glue[edit]

Summary[edit]

This is a basic geometry problem about circles.

Explanation[edit]

Two rings are glued together when the distance between two center is less than sum of radius ( dist <= r1+r2 ) and greater than the diff of radius ( dist >= fabs(r1-r2) ) A special case is two ring is totally overlap. (r1==r2 && center1==cneter2)

Gotchas[edit]

You must print "0 rings." when number of max component is 0.

Input[edit]

4
0.0 0.0 1.0
-1.5 -1.5 0.5
1.5 1.5 0.5
-2.0 2.0 3.5
3
3.0 2.0 2.0
0.0 -0.5 1.0
0.0 0.0 2.0
5
-2.0 0.0 1.0
1.0 -1.0 1.0
0.0 1.0 0.5
2.0 0.0 1.0
-1.0 1.0 1.0
-1

Output[edit]

The largest component contains 4 rings.
The largest component contains 2 rings.
The largest component contains 3 rings.