409695: GYM103687 J Frog

Grammy spotted a frog at the border of a circular pillar. The pillar is centered at $$$(0,0)$$$ and has radius $$$1$$$. The frog can jump to a distance of exactly $$$1$$$. Grammy wants the frog to move to her desired destination point at the border of the pillar. Please help Grammy to find a route for the frog with minimum number of jumps.

Note that the frog cannot be strictly inside the pillar at any time.

The input contains multiple test cases.

The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 10\,000$$$), indicating the number of test cases.

The only line of each testcase consists of two integers $$$d_s,d_t$$$ ($$$0 \leq d_s,d_t \leq 359$$$), indicating that the frog's starting position is $$$(\cos \dfrac{\pi d_s}{180}, \sin \dfrac{\pi d_s}{180})$$$, and the frog's destination is $$$(\cos \dfrac{\pi d_t}{180}, \sin \dfrac{\pi d_t}{180})$$$.

For each test case, print one or several lines in the following format.

The first line contains a single integer $$$k$$$, indicating the minimum number of jumps in this test case.

The next $$$k+1$$$ lines contain the landing points for the frog, including its starting point and its destination point.

The $$$i$$$-th of the next $$$k+1$$$ lines contains $$$2$$$ real numbers, indicating the coordinates of the frog's $$$i$$$-th landing point.

Your answer will be considered correct if all the following conditions are satisfied:

• The number of jumps is minimal.
• The distance between the first landing point and the starting point is less than $$$10^{-6}$$$.
• The distance between the last landing point and the destination point is less than $$$10^{-6}$$$.
• The distance $$$d$$$ between any two consecutive landing points satisfy $$$1-10^{-6}<d<1+10^{-6}$$$.
• The segment connecting any two consecutive landing points have a distance $$$d>1-10^{-6}$$$ to $$$(0,0)$$$.

3
0 0
0 90
180 0

0
1.0000000000 0.0000000000
2
1.0000000000 0.0000000000
1.0000000000 1.0000000000
0.0000000000 1.0000000000
4
-1.0000000000 0.0000000000
-1.0000000000 -1.0000000000
-0.0000000000 -1.0000000000
1.0000000000 -1.0000000000
1.0000000000 -0.0000000000