Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We are given P 2-D points (x1,y1),(x2,y2),(x3,y3),....(xP,yP).

There are total M number of Queries. Each query is in the form of a triplet.The format of each query is :

(a b d)

Let T be a triangle with vertices X(a+d,b),Y(a,b),Z(a,b+d).

For each of the M Queries, we have to return how many of the given points lie inside or on the boundary of triangle.

Example

P=5, M=3

The points(xi,yi) are :

1 3

1 5

3 6

4 4

2 6

The M Queries (format (a,b,d)) are:

1 5 3

1 5 4

1 1 1

Answer for above three queries are 3,3,0 respectively.

I tried to solve this problem using simple naive approach.But the constraints for the problem is indeed very large and are follows:

1 ≤ P ≤ 300000 1 ≤ M ≤ 200000

1 ≤ xi, yi ≤ 300000

1 ≤ a, b, d ≤ 300000

The Time Limit for this problem is just 1 Second.

How can i solve this problem within the given time-limit?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.