## Non-strategic Bombing

View as PDF

Points: 7
Time limit: 1.4s
Memory limit: 64M

Author:
Problem type

After losing their air-supremacy, Collea is being bombed continually by The Alliance. Collea has major cities and The Alliance has plans of attack. Due to poor planning, two cities may occupy the same position and the points chosen for an attack might not be unique. Also, due to virtually no difference in elevation, Collea can be represented as a 2 dimensional plane. In each plan of attack, The Alliance chooses any points in the country of Collea (not necessarily cities) and bombs the area inside the triangle formed by these three points. For each plan of attack, help the Collean government determine the number of cities that would be bombed for each of the plans. In particular, cities located on the edge of the triangle are also hit by the attack.

#### Constraints

The absolute values of the coordinates of any city or any attack are less than or equal to .

#### Input Specification

The first line contains two space-separated integers, and .
The next lines contain two integers, , the coordinates of the -th city.
The next lines contain three pairs of integers, which are the coordinates of the three points chosen for the -th attack.

#### Output Specification

Output lines, where the th line is the number of cities that would be bombed in the th plan.

#### Sample Input

3 3
1 1
2 2
3 3
1 1 3 3 0 5
1 7 2 3 5 2
0 0 1 2 2 1

#### Sample Output

3
1
1