题目描述

In a big, square room there are two point light sources: one is red and the other is green. There are also $n$ circular pillars.

Light travels in straight lines and is absorbed by walls and pillars. The pillars therefore cast shadows: they do not let light through. There are places in the room where no light reaches (black), where only one of the two light sources reaches (red or green), and places where both lights reach (yellow). Compute the total area of each of the four colors in the room. Do not include the area of the pillars.

输入格式

• One line containing the number of test cases, $T$.

Each test case contains, in order:

• One line containing the coordinates $x$, $y$ of the red light source.
• One line containing the coordinates $x$, $y$ of the green light source.
• One line containing the number of pillars $n$.
• $n$ lines describing the pillars. Each contains 3 numbers $x$, $y$, $r$. The pillar is a disk with the center $(x, y)$ and radius $r$.

The room is the square described by $0 \leq x, y \leq 100$. Pillars, room walls and light sources are all disjoint, they do not overlap or touch.

输出格式

For each test case, output:

Case #X:
black area
red area
green area
yellow area

where $X$ is the test case number, starting from 1, and each area is a real number.

Any answer with absolute or relative error of at most $10^{-5}$ will be accepted.

1
5 50
95 50
1
50 50 10

Case #1:
0.7656121
1437.986
1437.986
6809.104

提示

Limits

• All input numbers are integers.
• $1 \leq T \leq 15$
• $0 \leq x, y \leq 100$
• $1 \leq r \leq 49$

Small dataset(21 Pts)

• Time limit: 20 5 seconds.
• $0 \leq n \leq 1$

Large dataset(45 Pts)

• Time limit: 90 30 seconds.
• $0 \leq n \leq 50$