Triangles and Quadrangle

Little Yuan is two years old and she is learning about triangles and quadrangles. She is such a smart girl that she soon realizes two triangles that do not overlap each other can be joined to form a quadrangle. She picks up a lot of triangles and uses them to form quadrangles. Unfortunately, she is not good at this kind of jigsaw game yet and sometimes makes mistakes.

As her brother, you are curious whether she has made a mistake when forming a quadrangle from two triangles. Write a program to determine it.

In this problem a quadrangle is defined as a simple polygon with four vertices. You may also assume that every triangle and quadrangle has a positive area.

Two figures are considered the same if and only if one can be made to overlap the other completely by translation, rotation, and flipping (reflection).

The input contains multiple test cases. The first line contains a single integer $T$, the number of test cases. ($T \le 500$)

Each test case consists of 10 lines.

• The first $3 \times 2 = 6$ lines describe the two triangles. Each line contains two integers, the coordinates of one point; the first 3 lines are the first triangle and the next 3 lines are the second triangle.
• The next 4 lines describe the quadrangle, given in clockwise or counter-clockwise order.

All coordinates are less than $15000$ in absolute value.

For each test case, print one line. For the $i$-th test case, print the prefix Case #i: followed by Yes if the two given triangles can be joined without overlapping to form the given quadrangle, or No otherwise. For example, if the answer to the first test case is possible, print Case #1: Yes.