Triangular Queries

Problem code: TRIQUERY

All submissions for this problem are available.

You are given N lattice points (Xi, Yi), i = 1, 2, ..., N on a 2D Coordinate System.
You have to process Q queries, each query will be given as the form "x y d".
Let ABC be the triangle having vertices at A(x+d, y), B(x, y) and C(x, y+d).
For each query, you have to find how many of the given lattice points lie inside or on the boundary of the triangle ABC.

Input

The first line of the input contains two space-sparated integers N and Q.
Each of the following N lines have two space-sparated integers Xi, Yi giving the x and y coordinate of a lattice point.
Then the following Q lines contain three space-sparated integers x, y, d giving a query.

Output

For each query, output one integer on a line which denotes the number of the given lattice points which lie inside or on the boundary of the triangle.

Constraints

1 ≤ N ≤ 300000 (3 * 105)
1 ≤ Q ≤ 200000 (2 * 105)
1 ≤ Xi, Yi ≤ 300000 (3 * 105)
1 ≤ x, y, d ≤ 300000 (3 * 105)

Sample

Input 1:
5 3
1 3
1 5
3 6
4 4
2 6
1 5 3
1 5 4
1 1 1

Output 1:
3
3
0

Input 2:
2 2
1 5
3 7
2 5 6
2 3 4
 
Output 2:
1
0
Author: rustinpiece
Tester: laycurse
Editorial http://discuss.codechef.com/problems/TRIQUERY
Date Added: 4-11-2012
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

Is theoutpur of first test

gauravjasraj @ 1 Feb 2013 05:09 PM
Is theoutpur of first test case correct? Shoudn't it be 2 3 0 ?

No, it shouldn't be. Lattice

szekizoli @ 2 Feb 2013 05:55 AM
No, it shouldn't be. Lattice points 1 5, 2 6 and 3 6 lie inside or on the boundary of the triangle.

It seems like fastest people

ffanzhang @ 2 Feb 2013 12:16 PM
It seems like fastest people cannot get it under 1 sec. And also it seems the most general approach will give us the time limit exceeded error. I'm attempting a faster counting now :)

How come people who have

rahulkshwh @ 3 Feb 2013 12:38 AM
How come people who have exceeded time limit are being shown?

how come solutions with times

avinrox @ 3 Feb 2013 11:11 AM
how come solutions with times > 2s get accepted and my solution gets TLE with 1.01s? what am i missing?

@rahulkshwh @avinrox - The

ani94 @ 3 Feb 2013 11:34 AM
@rahulkshwh @avinrox - The time taken is the sum of the time taken for each test case file. The solns. have passed each file within Time Limit, so they have been accepted

no has solved it in C macimum

amitupadhyay @ 3 Feb 2013 02:09 PM
no has solved it in C macimum are getting TLE can anyone tell me why?

@admin can 6*10^10 operations

the_c0der @ 3 Feb 2013 04:14 PM
@admin can 6*10^10 operations be done under 1 sec on codechef server?

Can a lattice point be

sakuag333 @ 4 Feb 2013 01:04 AM
Can a lattice point be repeated more than once in the input ?

@sakuag333 : No point is

imran_adm @ 4 Feb 2013 05:09 PM
@sakuag333 : No point is given more than once

What is memory limit for this

deretin @ 5 Feb 2013 04:02 PM
What is memory limit for this problem?

how to approach this problem

lovelycse @ 7 Feb 2013 07:43 PM
how to approach this problem

timt limit exeeded ...

avanee @ 8 Feb 2013 07:35 AM
timt limit exeeded ...

are the given points in the

evandrix @ 8 Feb 2013 12:20 PM
are the given points in the input guaranteed to be distinct and integral?

@admin, I think there is two

zhouyuchen @ 8 Feb 2013 01:39 PM
@admin, I think there is two or more whitespace characters between some numbers in some cases.

@admin : I have been getting

xoticasb @ 10 Feb 2013 11:46 AM
@admin : I have been getting runtime error for this problem . Can you check my submissions for this problem ( ids- 1819753,1819743, 1817814 )?

Is it guaranteed that the

phantom11 @ 10 Feb 2013 02:42 PM
Is it guaranteed that the triangle will be formed ? Can there be a situation in which it goes out of constraints? For eg. x=y=d= 3*10^5

@phantom11 : I think the task

ivan100sic @ 10 Feb 2013 08:03 PM
@phantom11 : I think the task statement is quite clear, the coordinate system is infinite, and thus the triangle can always be formed.

SUCCESSFUL SUBMISSIONS


Fetching successful submissions