题目描述

一家小型计算机软件公司在开发其CAD软件时遇到了一个问题。该公司的老板在网上悬赏$1000美元，寻找能解决这个问题的人。你现在失业在家，希望通过你熟练的计算机编程技能赚取这笔钱。

问题相当简单：你的任务是计算两个可能重叠的形状的交集面积。这两个形状可以是矩形（Rectangle）或圆形（Circle）。

输入格式

• 第一行输入测试用例的数量。
• 每个测试用例包含两行，分别描述两个形状：
  • 如果是矩形，格式为 R x1 y1 x2 y2，表示左上角坐标为 $(x1, y1)$，右下角坐标为 $(x2, y2)$。
  • 如果是圆形，格式为 C x y r，表示圆心在 $(x, y)$，半径为 $r$。
• 所有输入的数字均为 $0$ 到 $10$ 之间的整数。

输出格式

对于每个测试用例，输出两个形状交集面积的最接近的整数。

输入样例 1

4
R 0 0 10 10
C 0 0 10

C 0 0 5
R 5 5 10 10

R 1 1 3 4
R 0 0 2 4

C 0 0 10
C 0 0 10

输出样例 1

79
0
3
314

来源

POJ Monthly