A1552.[COCI-2015_2016-olympiad]#3 Relay

A fleet of fishing boats set sail on the open sea from an Adriatic island. The position of each fishing boat is described with a point in the standard coordinate system, whereas the island is described with a convex polygon. The boats communicate via radio devices, and the island represents an obstacle for the radio waves. More precisely, if boat a transmits a message, then boat b receives the message if and only if the line segment connecting the positions of a and b does not cross the interior of the island (it is allowed to have the line segment touch the sides and vertices of the island).
Figure 3: In the first sample test, ships 2, 3, 4 and 7 will receive the original Mayday message, whereas ships 6 and 8 will receive the Relay message.
When ship a gets in trouble, it transmits the so-called Mayday message asking for help. All ships that receive the Mayday message immediately send the so-called Relay message repeating that ship a needs help. If a ship only receives the Relay message (and not the original Mayday message), then it sends nothing.
You are given the positions of n ships denoted with integers from 1 to n and the location of the island.
Ship number 1 has found itself in trouble and sends the Mayday message. Determine the total number of ships that will receive either the original Mayday message or any of the Relay messages.

The first line of input contains the integer n – the number of ships. The k th of the following n lines contains two integers xk and yk (−109 ≤ xk, yk ≤ 109 ) – the coordinates of the k th ship. All ships are located on different coordinates, not a single ship is located on a side or inside the polygon.
The following line contains the integer m – the number of vertices of the convex polygon describing the island. The k th of the following m lines contains two integers x 0 k and y 0 k (−109 ≤ x 0 k , y0 k ≤ 109 ) – the coordinates of the k th vertex of the polygon. The polygon’s vertices are given in the counter-clockwise direction and form a convex polygon. No two adjacent edges will be parallel.

You must output the required total number of boats that will receive one of the messages.

Subtask Score Limitations
1 18 1 ≤ n ≤ 300, 3 ≤ m ≤ 300
2 19 1 ≤ n ≤ 3000, 3 ≤ m ≤ 3 000
3 20 1 ≤ n ≤ 100 000, 3 ≤ m ≤ 300
4 43 1 ≤ n ≤ 100 000, 3 ≤ m ≤ 100 000