Spider web - MarisaOJ: Marisa Online Judge

Spider web

Time limit: 1000 ms
Memory limit: 256 MB
Reisen, during a picnic, discovered a spider web attached to a cliff. Upon closer observation, she realized that the rim of the web has the shape of a strict convex polygon with exactly $2n$ vertices. The vertices are given in clockwise order and are denoted respectively as $P_1, P_2, \dots, P_{2n}$. Reisen also noticed that there are $n$ “strange silk threads” on the web that were not created by the owner spider. Each strange thread is a straight line segment connecting two vertices of the polygon. Each vertex is an endpoint of exactly one strange thread. That is, the $2n$ vertices are paired into exactly $n$ threads. The owner spider starts from vertex $P_1$ and crawls along the boundary of the polygon clockwise. It passes through $P_2, P_3, \dots, P_{2n}$ in order, and when it returns to $P_1$ it ends its journey. While moving, the spider may stop at any time at any point on the boundary of the polygon, either exactly at a vertex or in the middle of an edge, to “shoot silk”. Each silk shot is described as follows: - The spider creates an infinite straight silk line starting from exactly the position where it is standing. - A strange silk thread is destroyed if the newly created line has at least one common point with the segment of that strange thread, including at an endpoint. Note that if the spider is standing on an edge of the polygon, then a strange thread lying exactly on that edge will also be destroyed in this shot. Reisen realized that if the spider does not shoot silk carefully, the journey may end while some strange threads are still stuck on the web. Help Reisen compute the minimum number of silk shots so that the spider can destroy all $n$ strange silk threads before finishing its journey. ### Input - The first line contains a positive integer $n$. - The next $2n$ lines where the $i$-th line contains two integers $x_i, y_i$, the coordinates of vertex $P_i$. - The next $n$ lines where each line contains two positive integers $u, v$ describing a strange silk thread connecting vertices $P_u$ and $P_v$. The data guarantees that the points $P_1, P_2, \dots, P_{2n}$ in the given order form a strict convex polygon in which no three vertices are collinear. Among the $n$ pairs $(u,v)$, each index from $1$ to $2n$ appears exactly once, and for every pair $(u,v)$. ### Output - Print a single integer which is the minimum number of silk shots needed to destroy all strange silk threads. ### Constraints - $1 \le n \le 2 \cdot 10^5$. - $|x_i|, |y_i| \le 10^{12}$ with all $i$. - $1 \le u, v \le 2n$ and $u \ne v$ for every pair $(u,v)$ above. ### Subtask - $10 \\%$ of the first tests have $n \le 3$. - $10 \\%$ of the next tests have $n \le 8$. - $15 \\%$ of the next tests have $n \le 20$. - $15 \\%$ of the next tests have $n \le 2 \cdot 10^3$. - $20 \\%$ of the next tests have $n \le 2 \cdot 10^4$. - $30 \\%$ of the remaining tests have no additional conditions. ### Example Input ``` 2 0 0 4 0 4 2 0 2 1 3 2 4 ``` Output ``` 1 ``` Input ``` 5 -2 1 -3 3 -2 5 0 6 3 6 5 5 6 3 5 1 3 0 0 0 1 3 2 4 5 7 6 9 8 10 ``` Output ``` 2 ``` ### Explaination - In sample test $1$, the two strange silk threads are the two diagonals of a rectangle; they intersect. The spider can stand at a point on the boundary and shoot a straight line passing through the intersection point of the two diagonals; then both strange threads are destroyed, so only $1$ shot is needed. - In sample test $2$, the strange silk threads are paired into many “alternating” segments around the polygon, so there is no single line that can intersect all of them simultaneously. However, the spider can shoot one line to destroy a group of strange threads at once, then shoot a second time to destroy all remaining threads, so at least $2$ shots are needed.