Problem H
Watch Your step
From Helldivers II
You are a helldiver going across the leftovers of your deployed minefield stratagem. You’ve noticed that there’s only two mines left on the way to the extraction from Mox. It was a difficult battle, but you have persevered and now you are on your way to extraction. While you are walking around the mines, you get curious about how many different ways are there for you to get to your destination from your initial position, while avoiding the mines. You limit yourself to only going right and up on a 2D plane.
Find the total number of paths you can take from your initial position to your final destination. It is guaranteed that the two mines do not occupy the same position and do not overlap with either the starting or final position.
Input
The input consists of a single line containing four integers pairs where $(x_i, y_i)$ are the initial coordinates, $(x_f, y_f)$ are the final coordinates ($0 \le x_i \le 128$, $0 \le y_i \le 128$, $x_i < x_f$, $y_i < y_f$), and the coordinates of the two mines ($x_{m_k}, y_{m_k}$) ($x_i < x_{m_k} < x_f$, $y_i < y_{m_k} < y_f, k \in \{ 1, 2\} $).
Output
Print the total number of paths.
| Sample Input 1 | Sample Output 1 |
|---|---|
0 0 7 7 3 3 4 4 |
1432 |
