Problem K
Keep the Parade Safe
The 1941 October Revolution Parade of
November
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
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.
Input
-
The first line of the input contains one integer
- the number of Nazi’s tropps. -
Each of the next
lines contains two integers and representing one point where a Nazi’s troop took place. -
The next line contains one integer
- the number of Soviet castles. -
Each of the next
lines contains two integers and representing position of one castle.
It is guaranteed that all given points are distinct.
Output
Write in one line the number castles which were in danger.
Sample Clarification
The
![\includegraphics[width=0.4\textwidth ]{sample.png}](/problems/parade/file/statement/en/img-0001.png)
The
![\includegraphics[width=0.4\textwidth ]{sample2.png}](/problems/parade/file/statement/en/img-0002.png)
Sample Input 1 | Sample Output 1 |
---|---|
4 0 1 3 7 4 5 6 5 9 1 4 1 6 2 3 2 5 3 5 3 6 4 8 5 4 6 3 |
4 |
Sample Input 2 | Sample Output 2 |
---|---|
4 1 2 3 2 5 2 2 5 2 3 4 2 3 |
0 |