OpenKattis
CS3233 Midterm Team Contest sponsored by Citadel | Citadel Securities

Start

2020-03-02 00:50 AKST

CS3233 Midterm Team Contest sponsored by Citadel | Citadel Securities

End

2020-03-02 05:20 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -268 days 7:28:35

Time elapsed

4:30:00

Time remaining

0:00:00

Problem F
Common Ground

Quibble Pants recently met his “special somepony” Clear Sky. To get closer to her, he wants to spend some quality time together with her daughter, Wind Sprint.

\includegraphics[width=0.4\textwidth ]{TBO_Buckball.png}
Figure 1: Illustration by Kyle Coate.

Unfortunately, while Wind Sprint is a huge sportspony, Quibble is anything but. Today, in an attempt to find some common ground, Quibble Pants bought VIP tickets for the three of them to a buckball tournament with the biggest stars in buckball: Team Ponyville!

All was going well until the half-time event, when, as a gift to the fans, Team Ponyville announced that they were going to randomly select a few members of the audience to play against them. Quibble and Wind Sprint were among those selected, and Quibble was chosen to be the team lead! He didn’t want to refuse, as he saw how excited Wind Sprint was, but he also doesn’t want to make himself look like an absolute fool in public. He needs your help!

The game of buckball is played in an arena of length $L$ and width $W$. Formally, the arena is the set of all points $(x, y)$ with $0 \leq x \leq L$ and $0 \leq y \leq W$.

There are $N$ players on each team. Every player has a position $(x, y)$ and a reach $r$. This means that all points $(x’, y’)$ in the arena satisfying

\begin{equation*} \left| x - x’ \right| + \left| y - y’ \right| \leq r \end{equation*}

are within the player’s reach.

\includegraphics[width=0.54\textwidth ]{explain1.png}
Figure 2: Illustration of Sample Input 1.

At the current moment in time, the $i^\text {th}$ player on Team Ponyville is at position $(X_ i, Y_ i)$ and has a reach of $R_ i$. The $i^\text {th}$ player on Team Quibble is at position $(X’_ i, Y’_ i)$ and has a reach of $R’_ i$.

A point in the arena is called covered by a team if it is within the reach of at least one player on that team. In buckball, as in many sports, it is not a good idea to leave opponents unguarded—hence it is necessary to ensure that points covered by the opponent’s team are also covered by yours. A point in the arena that is covered by both teams is called common ground.

To ensure that his team is not leaving the opponent’s team unguarded, Quibble needs to know: what proportion of points in the arena covered by Team Ponyville is common ground?

Input

The first line of input contains three integers, $N$ ($2 \leq N \leq 200\, 000$), $L$ ($1 \leq L \leq 10^9$) and $W$ ($1 \leq W \leq 10^9$), the number of players on each team, and the length and width of the arena, respectively.

The next $N$ lines of input contain the descriptions of the players on Team Ponyville. In particular, the $i^\text {th}$ of these lines contains three integers $X_ i$ ($0\leq X_ i \leq L$), $Y_ i$ ($0 \leq Y_ i \leq W$), and $R_ i$ ($1 \leq R_ i \leq 10^9$), denoting that the $i^\text {th}$ player on Team Ponyville is at position $(X_ i, Y_ i)$ and has a reach of $R_ i$.

The next $N$ lines of input contain the descriptions of the players on Team Quibble. In particular, the $i^\text {th}$ of these lines contains three integers $X’_ i$ ($0\leq X’_ i \leq L$), $Y’_ i$ ($0 \leq Y’_ i \leq W$), and $R’_ i$ ($1 \leq R’_ i \leq 10^9$), denoting that the $i^\text {th}$ player on Team Quibble is at position $(X’_ i, Y’_ i)$ and has a reach of $R’_ i$.

It is guaranteed that there are no two players at the same position.

Output

It can be shown that the proportion of points in the arena covered by Team Ponyville that is common ground can be uniquely represented as an irreducible fraction $p/q$, where $p$ and $q$ are non-negative integers with no common divisor greater than $1$.

Output the two integers $p$ and $q$ separated by a / on a single line by themselves.

Sample Input 1 Sample Output 1
3 10 7
4 1 2
7 4 3
2 7 2
5 3 2
8 4 1
2 5 1
8/29
Sample Input 2 Sample Output 2
2 10 10
1 1 1
2 2 1
8 8 1
9 9 1
0/1
Sample Input 3 Sample Output 3
2 10 10
1 1 1
2 2 1
8 8 100
9 9 100
1/1