SICRANO - Sicrano

Sicrano has a problem ... a geometry problem. He is not a very good in this area, so he's asking for your help.

Given a set of points and a set of segments, tell, for each segment, how much points lie in it.

Input

The first integer T (T <= 20) in the input says that there are T test cases in the input. Each test case begins with two integer N and M (1 <= N, M <= 50). N means how many points exists in that test case, and M means how many segments exists in that test case. The next N pairs of integers represents the points. Each pair describes the coordinates x and y of a point. (0 <= x, y <= 100). After that, the segments will be listed. Each segment is described by the coordinates of its two extreme points. All values in the input are integers. See the sample input for clarification.

Output

For each segment, print how many points are in it.

Example

Input:
1

4 3

1 1
2 2
3 3
4 4

0 0 5 5
3 3 4 4
0 0 1 0 Output: 4
2
0

Added by:Paulo Costa
Date:2012-01-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:UFPE

hide comments
2019-11-11 23:53:09
What vetox said! Not keeping that in mind cost me 40mins. Grmph.
2017-01-02 14:45:09
Make sure to make use of a small delta value (~0.000001) for tolerance when comparing two double values especially in Java.
2016-07-02 15:53:25 Piyush Kumar
I don't think it was absolutely vital to leave a spoiler in the comments, even with a star studded warning.
2016-02-12 06:43:36
ac in one go.....


dont read this its a spoiler........

************************Spoiler**************************
<snip>

Last edit: 2023-05-19 23:46:55
2014-05-20 14:33:17 agaurav77
Good Question, AC finally!
Focus on the necessary conditions for slopes and constraints of location of the three points :)
2013-06-09 03:25:49 strg
good ques.........finally got AC.........

2013-05-29 02:49:58 Akshat Jain
are same points considrd same or diff..???
2013-02-22 15:32:26 Ouditchya Sinha
Good question, finally AC :) ... no special cases, but consider all possibilities.
2012-09-07 15:30:25 numerix
1. Is a segment of length 0 a segment?
2. Are points with same coordinates considered as different or not?

After AC I can answer my own questions:
1. There is no segment with length 0 in the testdata.
2. Duplicate points are considered to be different.

And be aware: There are empty lines in between!

Last edit: 2012-09-07 16:06:43
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.