Problem K
Keep the Parade Safe

The 1941 October Revolution Parade of November $7^{th}$, 1941, taking place in Moscow, Soviet Union, was a parade in honor of the October Revolution 24 years ealier. It was one of the most memorable parade because of the serious circumstance at that time: Soviet’s forces had constantly been dominated since the last 4 months, and Moscow was surrounded by Nazi under an extremely high pressure. Many soldiers joined that parade, and immediately rushed into the battle field after then. The winning against Nazi later pushed Hitler’s forces very far away from Moscow and completely destroyed his Barbarossa plan…

In order to ensure safety for the parade, Stalin gathered information about the positions of Nazi’s troops. He knew that Nazi’s troops can be depicted as $N$ points on the Cartesian plane. He was also aware of $S$ Soviet’s defending castles, which can be represented by $S$ points.

Stalin thought that one castle was in danger, if there exist a group of four Nazi’s troops, which forms a non-degenerate quadrilateral and the castle lies inside or on its border. Recall that a quadrilateral is non-degenerate iff no three of its vertices are collinear, and its edges do not intersect (with the exception that edges can intersect at vertices). Stalin wanted to know how many castles were in danger, so that he can send a suitable protection for them.


  • The first line of the input contains one integer $N$ $(4 \leq N \leq 1\, 000)$ - the number of Nazi’s tropps.

  • Each of the next $N$ lines contains two integers $x$ and $y$ $(0 \leq x, y \leq 10^6)$ representing one point where a Nazi’s troop took place.

  • The next line contains one integer $S$ $(1 \leq S \leq 1\, 000)$ - the number of Soviet castles.

  • Each of the next $S$ lines contains two integers $x$ and $y$ $(0 \leq x, y \leq 10^6)$ representing position of one castle.

It is guaranteed that all given points are distinct.


Write in one line the number castles which were in danger.

Sample Clarification

The $1^{st}$ sample corresponds to the following figure. Blue points represent Nazi troops’ locations, oranges points represent in-danger castles, green points represent non in-danger castles.

\includegraphics[width=0.4\textwidth ]{sample.png}

The $2^{nd}$ sample corresponds to the following figure. Note that the quadrilateral is degenerated, so no castle is in danger.

\includegraphics[width=0.4\textwidth ]{sample2.png}
Sample Input 1 Sample Output 1
0 1
3 7
4 5
6 5
1 4
1 6
2 3
2 5
3 5
3 6
4 8
5 4
6 3
Sample Input 2 Sample Output 2
1 2
3 2
5 2
2 5
3 4
2 3

Please log in to submit a solution to this problem

Log in