Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Overlapped Shapes
Time Limit: 10000MSMemory Limit: 10000K
Total Submissions: 650Accepted: 185

Description

A small computer software company encountered a problem when developing their CAD software. The boss of this company offered a reward of $1000 on the Internet for the person who can solve this problem for them. You are now unemployed at home and want to earn the money by your proficient computer programming skill.

The problem is quite simple. Your task is just to calculate the area of the intersection of two shapes that may overlap. These two shapes both can be rectangles or circles.

Input

The first line of input is the number of test cases. For each test case, there are two lines describing two shapes. A line of "R x1 y1 x2 y2" represents a rectangle with top-left corner at (x1, y1) and bottom-right corner at (x2, y2). A line of "C x y r" represents a circle with center at (x, y) and radius r.

You can assume that all the numbers mentioned above are integers between 0 and 10.

Output

For each test case, print the nearest integer of the intersection area of the two shapes in a single line.

Sample Input

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

Sample Output

79
0
3
314

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator