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).
1
2
3
4
5
6
7
8
9
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-ca\)lled Mayday message asking for help. All ships that
receive the Mayday message immediately send the \(so-ca\)lled 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.

Subtask
Score
Limitations
1
18
\(1 \le n \le 300\), \(3 \le m \le 300\)
2
19
\(1 \le n \le 3000\), \(3 \le m \le 3\,000\)
3
20
\(1 \le n \le 100\,000\), \(3 \le m \le 300\)
4
43
\(1 \le n \le 100\,000\), \(3 \le m \le 100\,000\)

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\) (−\(10^{9} \le xk\), y\(k \le 10^{9}\)) – 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^{′}\)
{k} ^{and} ^{{y}
{(}{10} {≤}}}^{′
{k}^{, y}^{′}
^{≤}{9}} ^{–} ^{the
coordinates of the \(k^{th}\) vertex of the polygon. The polygon’s vertices are given in the count\(er-cl\)ockwise
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.
5 od 8

생성자가 기록되지 않았습니다.

출처 COCI 2015/2016 Olympiad