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

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.