A Colourful Prospect
Contest: Codeforces Round 462 (Div. 1)
Difficulty rating: 2700
Tags: geometry, graphs

Firecrackers scare Nian the monster, but they're wayyyyy too noisy! Maybe fireworks make a nice complement.

Little Tommy is watching a firework show. As circular shapes spread across the sky, a splendid view unfolds on the night of Lunar New Year's eve.

A wonder strikes Tommy. How many regions are formed by the circles on the sky? We consider the sky as a flat plane. A region is a connected part of the plane with positive area, whose bound consists of parts of bounds of the circles and is a curve or several curves without self-intersections, and that does not contain any curve other than its boundaries. Note that exactly one of the regions extends infinitely.

Input format:
The first line of input contains one integer n (1 ≤ n ≤ 3), denoting the number of circles.

The following n lines each contains three space-separated integers x, y and r ( - 10 ≤ x, y ≤ 10, 1 ≤ r ≤ 10), describing a circle whose center is (x, y) and the radius is r. No two circles have the same x, y and r at the same time.

Output format:
Print a single integer — the number of regions on the plane.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first example,

For the second example,

For the third example,

Example input:
3
0 0 1
2 0 1
4 0 1

Example output:
4

Example input:
3
0 0 2
3 0 2
6 0 2

Example output:
6

Editorial:
It seems the problem can be solved with case analysis at first sight. Okay let's try to do so...
For n = 1, it's trivial and the answer is, of course, 2.
For n = 2, there are two cases:
• If the two circles are intersect, the answer is 4;
• Otherwise, the answer is 3.
For n = 3... well I think it's really a tough job, so think about general case will probably make our lives better.
The main solution is based on Euler's formula for planar graph. This formula tells us that if we denote the number of vertices in a connected graph by v, the number of edges by e and the number of faces (or regions) by f, we have f = e - v + 2. Since the circles can form several components, denoted the number of which by c, the formula for general planar graph should be f = e - v + c + 1.
So what we need to do is to calculate v, e, and c. It's easy to see that v is the number of unique intersection between circles. As for e, we can calculate the number of edges on each circle, which is equal to the unique intersection on each circle. The only special case is a single circle, and we can consider it as a graph without vertices and edges but forms one component, or a vertex with an edge to itself. Anyway it doesn't matter when v = e. The last one is c, which can be obtained easily with the help of dsu or dfs/bfs.
The total complexity is $$O(n^2 \log n)$$, but why I leave this special case as a problem instead of a general case? Reread the first sentence of this tutorial and you will get the answer :)
Here I want to show you the test #113, which is made by hands.
Guess how many regions in this graph?
Bonus. Construct three circles within the given constraints that share one common intersection with at least one non-integral coordinate.
And also, unfortunately, this problem coincides with this problem and I am really sorry for this issue.