Non-strategic Bombing

View as PDF

Submit solution

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

Problem type

After losing their air-supremacy, Collea is being bombed continually by The Alliance. Collea has N major cities and The Alliance has M 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 3 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.


1 \le N, M \le 100
The absolute values of the coordinates of any city or any attack are less than or equal to 10^5.

Input Specification

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

Output Specification

Output M lines, where the ith line is the number of cities that would be bombed in the ith 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



  • 0
    Medi  commented on Jan. 7, 2019, 1:34 p.m.

    Are the points always given in counter-clockwise order?