SICRANO - Sicrano

no tags 

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

hide comments
vetox: 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.

Piyush Kumar: 2016-07-02 15:53:25

I don't think it was absolutely vital to leave a spoiler in the comments, even with a star studded warning.

rishabh_1997: 2016-02-12 06:43:36

ac in one go.....


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

************************Spoiler**************************


1. Point should lie on the line.
2. Sum of distance of point from both ends must be equal to distance between two ends.

agaurav77: 2014-05-20 14:33:17

Good Question, AC finally!
Focus on the necessary conditions for slopes and constraints of location of the three points :)

strg: 2013-06-09 03:25:49

good ques.........finally got AC.........

Akshat Jain: 2013-05-29 02:49:58

are same points considrd same or diff..???

Ouditchya Sinha: 2013-02-22 15:32:26

Good question, finally AC :) ... no special cases, but consider all possibilities.

numerix: 2012-09-07 15:30:25

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
akb: 2012-09-06 12:19:05

Don't know why i read the comment before solving it...:(


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