Time Limit: 2 sec
Memory Limit: 64 MB
Attempts: 0
Accuracy: 0.00%
Author: Akashdeep Goel

â€˜Siddharthâ€™ and â€˜Sunitâ€™ were playing pacman :

The game contains a specie with the following shape (and orientations).

(Rightward opening)

(Upward opening)

(Downward opening)

(Leftward opening)

While playing the game, â€˜Siddharthâ€™ started thinking to develop a new version of this game which will have multiple pacmans in the arena. He thinks to give different varieties of packmans also, each one with different powers. To differ the shape of one variety with another, he decides to change the angle at which the mouth opens, for each variety. But, immediately he wondered that how much area will be covered by this yellow color on the total screen. (Assume that there is no black circle (as eye) inside the boundary).

So, he wrote a program to calculate this yellow covered area and asked â€˜Sunitâ€™ to give him some test cases containing:

- position of pacman (integer coordiantes)
- its radius (integer radius)
- half of the angle at which mouth opens (angle in radians)
- direction in which mouth is open. ( â€˜nâ€™ for upward opening; â€˜sâ€™ for downward opening; â€˜eâ€™ for rightwards opening; â€˜wâ€™ for leftward opening; â€˜xâ€™ for no opening â€“ closed mouth;)

But, â€˜Sunitâ€™ gave him some cases in which, some pacmans were colliding.

**NOTE:** Collision is defined here, as an overlap of YELLOW COLOURED AREA. e.g the below one is not a collision

Seeing this, Siddharth thought an interesting problem now â€“ What maximum area can be obtained by using some (or all) of the given pacmans without any two of them having collision.

Note that the arena has vertical and horizontal paths only, and pacman must fit in these paths so only the pacmans in a common vertical or horizontal path can collide i.e two colliding pacman must have their centres on the same verticle line or same horizontal line. A sample is shown below:

**INPUT FORMAT:**

Line 2: n

Line 3: x1 y1 r1 theta1 d1

.....

.....

Line n+2: xn yn rn thetan dn

Line n+3: nâ€™

.....

.....

t = number of test cases */

n = number of given pacmans */

x1 = x coordinate of centre of first pacman;

y1 = y coordinate of centre of first pacman;

r1 = radius of ciicular boundary of first pacman;

theta1 = half of the angle of open mouth of first pacman;

d1 = direction of mouth opening

/* data for nth pacman */

/* data for next test case */

**CONSTRAINTS:**

Use pi = 3.14159265;

1<= t <=10

// t is an integer

1<= n <=100

// n is an integer

-1000<= x, y <=1000

// x and y are integers

r<=1000

// r is an integer

theta<= pi/2

// theta is in radians

d is one of these {â€˜nâ€™, â€˜sâ€™, â€˜eâ€™, â€˜wâ€™, â€˜xâ€™}

**OUTPUT FORMAT:**

Line 1: a1

/* answer for first test case, print answers up to the second place after decimal point, rounded at the second place after decimal point */

Line 2: a2

.....

.....

Line t: at

**EXAMPLE:
INPUT:**

5

3

0020x

5020x

8060x

2

0 0 10 1.5 e

5010x

2

0 0 2 1.5 e

2 0 2 1.5 w

2

0 0 2 1.3 e

1 0 2 1.3 w

2

0 0 2 0.2 n

0220x

**OUTPUT:**

125.66

167.30

13.13

14.73

12.57

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED