P5467 [PKUSC2018] PKUSC

Jiutiao Keliang is a girl who loves playing games. Recently, she has been playing a hack-and-slash mowing game. There are $n$ enemies on the plane, and the coordinates of each enemy are $x_i,y_i$. Keliang has a skill that allows her to draw a simple polygon with $m$ points on the plane, and eliminate all enemies that are **strictly** inside the polygon. It is not hard to see that if she wants to eliminate enemies quickly, she can just draw a sufficiently large simple polygon. But that would make the game much less fun. So, Keliang decides to add some randomness to the game. Keliang casually draws a simple polygon with $m$ points $(a_i,b_i)$ on the plane. Next, she plans to randomly choose a number $\alpha$ according to the uniform distribution on $[-\pi,\pi)$ (you can think of it as choosing with equal probability), and rotate this simple polygon counterclockwise around the origin by an angle of $\alpha$ (in radians). Now Keliang gives you the coordinates of every point and the polygon. Your task is to help Keliang compute the expected number of enemies she can eliminate after a random rotation.

The first line contains four integers $n,m$. The next $n$ lines each contain two integers $x_i,y_i$, describing the coordinates of an enemy. The next $m$ lines each contain two integers $a_i,b_i$, describing each vertex of the simple polygon in counterclockwise order.

Output one line with one number representing the expected value, rounded to five digits after the decimal point. It is guaranteed that, before rounding, the $6$-th digit after the decimal point will not be $4$ or $5$ for all testdata.

### Sample Explanation If you are not very familiar with probability and expectation, here are some hints: 1. Let $P_i$ be the probability that after rotation, exactly $i$ enemies can be eliminated. Then the expectation is $\sum_{i=1}^n iP_i$. 2. One way to compute $P_i$ is: among all rotation angles in the range $[-\pi,\pi)$, the angles for which exactly $i$ enemies are eliminated after rotation form $t_i$ intervals $(l_j,r_j)$ (whether endpoints are open or closed does not matter). Then $P_i=\frac{\sum_{j=1}^{t_i}(r_j-l_j)}{2\pi}$. In this problem: the intervals where $0$ enemies can be eliminated are $[\frac{\pi}{2},\pi),[-\pi,-\frac{\pi}{2}]$, and the intervals where $1$ enemy can be eliminated are $(-\frac{\pi}{2},0),(0,\frac{\pi}{2})$. Therefore, $P_0 = P_1=\frac{1}{2}$. So the answer is $\frac{1}{2}=0.50000$. ### Constraints For $30\%$ of the data, $n,m \leq 15$. For another $30\%$ of the data, the chosen simple polygon is a convex polygon. For $100\%$ of the data, $n \leq 200, m \leq 500, |x|,|y| \leq 10^6$. Translated by ChatGPT 5