It's a ****ing boat, and it's full of pirates
Captain Oliver is plotting a new expedition for his pirate crew. His navigation skills aren't the strongest, so he decided to randomly choose a point on the shore and a direction. He is now curious about his probability of reaching the opposite shore across the sea. He has now asked for your help to determine this probability by modeling it as a geometry problem!
He has modeled each shore as a polyline in the Cartesian plane, each starting at $$$x = 0$$$ and ending at the same value of $$$x$$$. Since the shores are separated by a sea, it is guaranteed that the maximum y value of the starting shore is strictly less than the minimum y of the ending shore. In addition, there are no bays; therefore, it is guaranteed that for each polyline, the x values of the points are strictly increasing.
Captain Oliver will then pick a point $$$p$$$ uniformly randomly on the starting polyline. Let $$$\vec{n}$$$ be the normal vector to the segment that $$$p$$$ is on, pointing towards the sea (i.e., it has a positive y component). Relative to $$$\vec{n}$$$, he will then pick an angle, $$$\theta$$$ ($$$-\frac{\pi}{2} \leq \theta \leq \frac{\pi}{2}$$$), with a probability density function of $$$\frac{\cos(\theta)}{2}$$$. The boat's trajectory is then the ray starting at $$$p$$$ and traveling at angle $$$\theta$$$, in respect to $$$\vec{n}$$$. A trajectory reaches the opposite shore if it intersects the ending polyline and only intersects the starting polyline at $$$p$$$.
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$2 \leq n, m \leq 10^6$$$) — the number of points on the starting shore's polyline, and the number of points on the ending shore's polyline.
The following $$$n$$$ lines will each contain two integers, $$$x_{s, i}$$$ and $$$y_{s, i}$$$ ($$$0 \leq x_{s, i}, y_{s, i} \leq 10^9$$$) — the $$$i$$$-th point on the starting shore's polyline. It is guaranteed that $$$x_{s, i} \lt x_{s, i+1}$$$ for all $$$i \in [1, n-1]$$$.
The following $$$m$$$ lines will each contain two integers, $$$x_{e, i}$$$ and $$$y_{e, i}$$$ ($$$0 \leq x_{e, i}, y_{e, i} \leq 10^9$$$) — the $$$i$$$-th point on the ending shore's polyline. It is guaranteed that $$$x_{e, i} \lt x_{e, i+1}$$$ for all $$$i \in [1, m-1]$$$.
It is guaranteed that the maximum value of $$$y_{s, i}$$$ is strictly less than the minimum value of $$$y_{e, i}$$$ and that $$$x_{s,1} = x_{e,1} = 0$$$ and $$$x_{s,n} = x_{e,m}$$$.
Output a single real number — the probability that the trajectory successfully reaches the ending shore. Your answer will be accepted if it has an absolute or relative error of $$$10^{-6}$$$ with the judge's solution.
3 30 01 32 00 41 52 4
0.0911512657
5 70 02 23 14 26 00 61 32 43 74 45 36 6
0.3715825446
