0205. Circles

Input file name:	circles.in
Output file name:	circles.out
Time limit:	2 s
Memory limit:	64 megabytes

Consider N different circles on the plane. They divide it to several parts, you have to find the number of these parts.

For the purpose of this problem the circle of radius r with center (x₀, y₀) is the set of points C={(x, y) | (x - x₀)²+(y - y₀)² = r² }.

Input file

The first line of the input file contains N – the number of circles (1 ≤ N ≤ 50). Next N lines contain three integer numbers x₀, y₀, and r each – the coordinates of the center and the radius of the circle.

All coordinates do not exceed 10³ by their absolute value, all radii are positive and do not exceed 10³.

No two circles coincide.

Output file

First output K – the number of parts circles divide the plane to.

Due to floating point precision losses possible, do not consider parts with area not exceeding 10^-10.

Examples:

circles.in	circles.out
2 0 0 3 0 0 2	3

Source: Petrozavodsk Winter 2004. Andrew Stankevich Contest 4, Friday, January 30
Author: Andrew Stankevich

Discuss       Submit a solution



Printable version