Alan and Brian want to live in Fantasy City.
They need to choose two house to live.
Fantasy City can be represent as an cartesian coordinate plane.
And all of houses are located on lattice point, in other words, both of x and y coordinates are integers.
But they want to contact to each other with radio.
And the radio's effective range is $d$.
So they want to choose two houses and their distance is less than or equal to $d$.
Please help them to calculate how many choices they can choose.
For example:
In this picture, there are $5$ points which are houses.
$(0,0),(3,2),(-1,-3),(3,0),(-2,1)$
Assume that the effective range $d=3$.
Then they have $3$ choices to choose.
$distance(A,B)=\sqrt{(3-0)^ 2+(0-0)^ 2}=\sqrt{9}\leq3$
$distance(B,D)=\sqrt{(3-3)^ 2+(2-0)^ 2}=\sqrt{4}\leq3$
$distance(A,E)=\sqrt{(0+2)^ 2+(1-0)^ 2}=\sqrt{5}\leq3$
Any two different houses are on different point.
First line contains two integers $N$ and $d$, which represent the total number of houses and the effective range of radio.
Following $N$ lines, each line contains two intergers $x$ and $y$ seperated by a space, which are x-coordinate and y-coordinate respectively.
One line contains an integer - the number of choices.
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~7 | All of houses are on x-axis | 5 |
2 | 0~15 | No specified restriction | 10 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 |