Algorithms
Medium
2857
2953
Count Pairs of Points With Distance k
count-pairs-of-points-with-distance-k
"""
You are given a 2D integer array coordinates and an integer k, where coordinates[i] = [xi, yi] are the coordinates of the ith point in a 2D plane.

We define the distance between two points (x1, y1) and (x2, y2) as (x1 XOR x2) + (y1 XOR y2) where XOR is the bitwise XOR operation.

Return the number of pairs (i, j) such that i < j and the distance between points i and j is equal to k.

Example 1:

Input: coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
Output: 2
Explanation: We can choose the following pairs:
- (0,1): Because we have (1 XOR 4) + (2 XOR 2) = 5.
- (2,3): Because we have (1 XOR 5) + (3 XOR 2) = 5.

Example 2:

Input: coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
Output: 10
Explanation: Any two chosen pairs will have a distance of 0. There are 10 ways to choose two pairs.


Constraints:

 * 2 <= coordinates.length <= 50000
 * 0 <= xi, yi <= 106
 * 0 <= k <= 100
"""
class Solution:
    def countPairs(self, coordinates: List[List[int]], k: int) -> int:
        
You are given a 2D integer array coordinates and an integer k, where coordinates[i] = [xi, yi] are the coordinates of the ith point in a 2D plane.

We define the distance between two points (x1, y1) and (x2, y2) as (x1 XOR x2) + (y1 XOR y2) where XOR is the bitwise XOR operation.

Return the number of pairs (i, j) such that i < j and the distance between points i and j is equal to k.

Example 1:

Input: coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
Output: 2
Explanation: We can choose the following pairs:
- (0,1): Because we have (1 XOR 4) + (2 XOR 2) = 5.
- (2,3): Because we have (1 XOR 5) + (3 XOR 2) = 5.

Example 2:

Input: coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
Output: 10
Explanation: Any two chosen pairs will have a distance of 0. There are 10 ways to choose two pairs.


Constraints:

 * 2 <= coordinates.length <= 50000
 * 0 <= xi, yi <= 106
 * 0 <= k <= 100


Please complete the code below to solve above prblem:
```python
class Solution:
    def countPairs(self, coordinates: List[List[int]], k: int) -> int:
        
```

my_solution = Solution()

test_input = { "coordinates": [[1,2],[4,2],[1,3],[5,2]], "k": 5 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "coordinates": [[1,3],[1,3],[1,3],[1,3],[1,3]], "k": 0 }
assert my_solution.countPairs(**test_input) == 10

test_input = { "coordinates": [[27,94],[61,68],[47,0],[100,4],[127,89],[61,103],[26,4],[51,54],[91,26],[98,23],[80,74],[19,93]], "k": 95 }
assert my_solution.countPairs(**test_input) == 5

test_input = { "coordinates": [[39,29],[98,59],[65,77],[41,26],[95,12],[71,66],[41,93],[28,33],[96,40],[39,8],[106,54],[8,49],[68,59],[21,15],[3,66],[77,85],[111,51]], "k": 21 }
assert my_solution.countPairs(**test_input) == 6

test_input = { "coordinates": [[100,32],[69,8],[85,31],[69,47],[62,34],[102,43],[81,39],[90,0],[123,6],[79,18],[21,94],[13,36],[49,97],[76,59],[42,74],[60,68],[21,11],[71,21],[64,13],[64,95],[5,85],[118,53],[70,44],[38,57],[32,119],[80,61],[13,68],[43,108],[86,49]], "k": 39 }
assert my_solution.countPairs(**test_input) == 20

test_input = { "coordinates": [[60,55],[35,32],[99,2],[58,57],[16,2],[43,28],[30,35],[35,83],[104,41],[20,69],[58,14],[12,92],[71,49],[7,82],[65,68],[9,40],[15,56],[57,46],[21,8],[37,64],[42,94],[73,91],[12,121],[10,21],[41,89]], "k": 54 }
assert my_solution.countPairs(**test_input) == 10

test_input = { "coordinates": [[94,23],[86,58],[126,55],[107,23],[121,60],[89,28],[123,15],[127,3],[100,49],[5,3],[81,49],[93,0],[95,37],[92,25]], "k": 53 }
assert my_solution.countPairs(**test_input) == 18

test_input = { "coordinates": [[40,54],[8,68],[33,11],[51,93],[95,95],[17,53],[35,39],[59,42],[28,63],[41,63],[54,0],[88,31],[5,107],[32,124],[74,64],[15,27],[61,92],[16,47],[62,22],[2,28],[27,14],[53,39],[21,91],[7,11]], "k": 60 }
assert my_solution.countPairs(**test_input) == 11

test_input = { "coordinates": [[28,14],[2,13],[28,14],[4,7],[23,1],[54,0],[43,22],[98,16]], "k": 33 }
assert my_solution.countPairs(**test_input) == 5

test_input = { "coordinates": [[84,92],[84,92],[84,92],[84,92],[84,92],[54,59],[84,92],[93,44]], "k": 0 }
assert my_solution.countPairs(**test_input) == 15

test_input = { "coordinates": [[10,57],[12,62],[92,44],[7,60],[8,55],[13,50],[5,55],[71,82],[64,26],[68,43],[61,88],[9,44],[95,16],[17,16],[12,53],[9,59],[81,44],[3,56],[70,94],[0,58],[84,29],[13,63],[79,87],[19,39],[74,35],[92,7],[31,6],[2,50]], "k": 13 }
assert my_solution.countPairs(**test_input) == 19

test_input = { "coordinates": [[56,47],[26,50],[51,2],[40,7],[24,34],[55,2],[13,92],[57,50],[47,35],[32,96],[14,0],[4,84],[86,95]], "k": 56 }
assert my_solution.countPairs(**test_input) == 4

test_input = { "coordinates": [[34,60],[17,93],[87,90],[32,125],[71,27],[27,26],[127,115],[91,27],[63,68],[97,48],[69,73],[120,78],[43,55],[101,125],[86,87],[12,35],[5,20],[46,12],[17,24],[107,62],[86,88],[26,80],[30,41],[110,114]], "k": 81 }
assert my_solution.countPairs(**test_input) == 17

test_input = { "coordinates": [[65,19],[12,80],[90,64],[38,68],[17,25],[49,36],[91,47],[20,31],[81,54],[83,20],[90,100],[0,6],[93,121]], "k": 36 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "coordinates": [[24,75],[22,67]], "k": 23 }
assert my_solution.countPairs(**test_input) == 0

test_input = { "coordinates": [[42,32],[62,60],[57,61],[100,56],[91,62],[57,21],[100,56],[63,63],[45,52],[59,75],[32,61],[57,43],[61,57],[64,52],[24,54],[92,15],[53,25],[84,63],[1,18],[21,57],[29,9],[68,91],[22,43],[105,27]], "k": 48 }
assert my_solution.countPairs(**test_input) == 18

test_input = { "coordinates": [[70,98],[79,66],[71,63],[111,94],[3,50],[64,111],[98,67],[23,41],[66,14],[40,19],[15,13],[32,86],[59,58],[73,94],[18,10],[77,50],[20,60],[66,8],[15,30],[71,2],[55,9]], "k": 60 }
assert my_solution.countPairs(**test_input) == 7

test_input = { "coordinates": [[5,100],[60,9],[84,65],[38,66],[83,35],[17,80],[88,76],[80,101],[55,74],[46,62],[28,73],[54,40],[119,71],[10,94],[45,82],[20,90],[47,27],[41,97],[66,5],[33,0],[101,5],[89,125],[6,58],[61,107],[25,17],[104,0],[29,2]], "k": 73 }
assert my_solution.countPairs(**test_input) == 15

test_input = { "coordinates": [[29,23],[8,19],[26,5],[12,25],[37,2],[37,27],[18,68],[3,53],[81,85],[27,94],[29,39],[41,64],[26,28],[23,80],[13,46],[5,68],[16,18],[21,77]], "k": 25 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "coordinates": [[90,31],[113,54],[92,36],[67,49],[123,124],[127,112],[16,24],[85,50],[58,94],[115,48],[83,30],[51,112],[39,23],[0,21],[27,44],[99,100],[122,63],[34,39],[25,48],[44,49],[84,97],[31,61]], "k": 84 }
assert my_solution.countPairs(**test_input) == 10

test_input = { "coordinates": [[51,47],[51,47],[8,14],[82,68],[55,85],[8,14],[51,47],[87,97],[75,65],[78,10],[51,47],[87,97],[74,19],[51,47],[56,66],[8,14],[78,10],[74,66],[65,92],[51,47],[3,31]], "k": 0 }
assert my_solution.countPairs(**test_input) == 20

test_input = { "coordinates": [[25,82],[86,89],[25,82],[47,118],[14,58],[22,51],[0,93],[26,9],[67,27],[43,22],[78,49],[82,15],[93,22],[67,34],[54,43],[61,55],[74,77],[115,108],[54,55],[9,30],[31,3],[26,5],[60,49]], "k": 90 }
assert my_solution.countPairs(**test_input) == 22

test_input = { "coordinates": [[29,23],[48,3],[58,62],[16,19],[0,30],[59,5],[96,50],[7,46],[5,18],[42,32],[78,55]], "k": 17 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "coordinates": [[47,68],[55,68],[36,73],[33,70],[36,81],[60,81],[32,18],[38,95],[34,75],[33,5],[33,78],[32,10],[36,93],[56,77],[43,17],[99,70],[15,77],[42,87],[30,18],[36,56],[47,68],[45,70],[48,77],[53,94],[0,86],[53,9],[68,35],[32,77],[95,90]], "k": 24 }
assert my_solution.countPairs(**test_input) == 31

test_input = { "coordinates": [[5,100],[19,21],[83,36],[24,59],[92,49],[6,73],[57,78],[69,33],[3,81],[53,59],[23,40],[6,21],[57,55],[98,43],[33,15],[8,83],[29,29],[85,41],[47,64],[10,32],[82,94],[14,29],[13,99],[19,20],[85,108],[41,9]], "k": 78 }
assert my_solution.countPairs(**test_input) == 12

test_input = { "coordinates": [[8,94],[19,13],[72,75],[17,8],[57,45],[17,15],[14,95],[74,78],[17,15],[9,95],[79,76],[13,91],[28,76],[94,12],[11,90],[94,11],[94,11],[15,89],[20,13],[23,14],[22,8],[21,71]], "k": 7 }
assert my_solution.countPairs(**test_input) == 24

test_input = { "coordinates": [[37,76],[109,71],[66,1],[55,6],[90,22],[71,24],[3,19],[46,24],[74,74],[85,94],[2,96],[1,48],[31,86],[22,78],[93,80],[3,112],[11,11],[98,18],[81,86],[55,54],[82,18],[127,23]], "k": 83 }
assert my_solution.countPairs(**test_input) == 11

test_input = { "coordinates": [[9,25],[56,25],[7,58],[9,48],[77,55],[6,10],[33,98],[22,26],[41,57],[18,4],[40,74]], "k": 49 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "coordinates": [[91,12],[86,8],[74,12],[85,58],[65,10],[49,51],[43,83],[34,91],[89,63],[26,44],[68,6],[71,8],[92,12],[49,79],[64,26],[0,87],[22,85],[15,72],[17,54],[33,37],[70,9],[88,95],[85,67],[32,85],[94,69],[87,77]], "k": 17 }
assert my_solution.countPairs(**test_input) == 16

test_input = { "coordinates": [[54,60],[31,62],[76,56],[79,44]], "k": 52 }
assert my_solution.countPairs(**test_input) == 0

test_input = { "coordinates": [[41,13],[15,74],[43,51],[44,10],[49,72],[63,48],[50,40],[90,86],[105,13],[11,118],[55,8],[3,39],[27,3],[55,72],[33,98],[10,59],[40,45],[10,59],[40,30],[97,43],[96,55],[47,32],[43,86],[57,61],[1,64]], "k": 64 }
assert my_solution.countPairs(**test_input) == 23

test_input = { "coordinates": [[29,96],[82,101],[1,88],[9,100],[55,42],[37,77],[89,95],[40,10],[111,114],[89,53],[91,33],[93,18],[90,14],[50,49],[27,91],[99,92],[26,15],[69,17],[61,64]], "k": 84 }
assert my_solution.countPairs(**test_input) == 7

test_input = { "coordinates": [[57,88],[83,2],[82,23],[19,7],[43,84],[54,87],[51,38],[61,68],[68,31],[74,49],[64,80],[2,19],[18,73],[52,73],[75,26],[32,71],[91,83],[84,15],[49,76]], "k": 30 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "coordinates": [[34,96],[53,25],[97,70],[48,31],[48,20],[54,26],[42,99],[52,24],[56,100],[35,106],[16,71],[34,69],[42,72],[28,8],[35,97],[103,67],[12,81],[8,86]], "k": 11 }
assert my_solution.countPairs(**test_input) == 10

test_input = { "coordinates": [[60,56],[48,34],[21,82],[63,26],[97,51],[35,63],[39,29],[5,46],[16,115],[19,71],[34,54],[6,65],[11,21],[54,66],[2,103],[13,64],[30,73],[23,58],[31,75],[6,63],[16,66],[21,100]], "k": 38 }
assert my_solution.countPairs(**test_input) == 10

test_input = { "coordinates": [[5,28],[16,39],[38,16],[21,34],[5,22],[73,52],[3,24],[24,37],[11,26]], "k": 10 }
assert my_solution.countPairs(**test_input) == 5

test_input = { "coordinates": [[34,76],[50,71],[55,74],[36,6],[56,77],[56,86],[9,25],[7,38],[34,76],[96,85],[29,32]], "k": 27 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "coordinates": [[69,99],[60,80],[59,72],[74,67],[34,78],[73,95],[65,72],[86,64],[42,89],[90,25],[84,48]], "k": 31 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "coordinates": [[50,75],[84,10],[3,1],[8,12],[41,82],[68,39],[55,31],[4,103],[50,19],[15,85],[20,50],[118,81],[47,14],[1,40],[1,58],[8,58],[18,110],[62,10],[98,69],[25,31],[99,10],[74,29],[124,73]], "k": 98 }
assert my_solution.countPairs(**test_input) == 15

test_input = { "coordinates": [[65,100],[43,13],[80,116],[40,82],[50,5],[53,14],[62,16],[38,8],[83,107],[56,11],[82,92],[62,16],[59,21],[38,8],[55,50],[67,76],[36,65]], "k": 33 }
assert my_solution.countPairs(**test_input) == 14

test_input = { "coordinates": [[52,32],[42,21],[1,56],[93,52],[85,87],[14,58],[39,21],[3,105],[18,13],[5,119],[108,77],[91,81],[22,71],[76,39],[2,59],[23,54],[83,26],[28,23],[33,69],[27,91],[92,19],[53,5],[39,32],[14,124]], "k": 83 }
assert my_solution.countPairs(**test_input) == 21

test_input = { "coordinates": [[84,63],[92,55],[56,94],[89,27],[53,93],[85,80],[65,91],[77,16],[28,99],[48,86],[54,44],[33,47],[47,10],[11,62],[2,17]], "k": 16 }
assert my_solution.countPairs(**test_input) == 4

test_input = { "coordinates": [[78,84],[91,79],[1,35],[73,76],[89,92],[69,94],[78,1],[27,71],[17,58],[18,33],[82,67],[24,59],[23,53],[82,86]], "k": 21 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "coordinates": [[29,53],[40,74],[42,73],[24,53],[79,50],[13,7],[43,72],[26,54],[41,75],[66,27],[43,72],[81,75],[47,73],[74,43],[97,60],[42,76],[46,77],[21,69],[88,77]], "k": 5 }
assert my_solution.countPairs(**test_input) == 16

test_input = { "coordinates": [[21,95],[53,15],[71,7],[22,40],[8,89],[66,62]], "k": 74 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "coordinates": [[93,3],[89,13],[70,48],[75,6],[43,82],[121,49],[80,1],[122,45],[57,45],[96,96],[86,82],[46,62],[63,79],[10,6],[55,36],[63,61],[79,99]], "k": 92 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "coordinates": [[0,36],[77,49],[25,41]], "k": 98 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "coordinates": [[42,18],[48,0],[64,62],[61,7],[33,51],[50,26],[1,91],[24,92]], "k": 44 }
assert my_solution.countPairs(**test_input) == 4

test_input = { "coordinates": [[69,94],[83,39],[2,37],[117,117],[82,54],[20,84],[91,88],[67,63],[43,69],[109,42],[9,69],[46,42],[60,99],[69,74],[81,80],[12,19]], "k": 91 }
assert my_solution.countPairs(**test_input) == 11

test_input = { "coordinates": [[75,44],[90,42],[62,96],[80,91],[82,78],[77,42]], "k": 23 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "coordinates": [[81,20],[74,53],[70,49],[99,66],[11,88]], "k": 60 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "coordinates": [[33,37],[35,52],[49,38],[47,32],[98,98],[84,83],[50,54],[45,34],[105,106],[54,44],[80,57],[96,80],[83,81],[36,22]], "k": 19 }
assert my_solution.countPairs(**test_input) == 7

test_input = { "coordinates": [[45,38],[47,5],[13,69],[88,65],[123,11],[15,30],[91,45],[66,100],[25,50],[63,10],[46,70],[36,77],[27,9],[78,91]], "k": 98 }
assert my_solution.countPairs(**test_input) == 6

test_input = { "coordinates": [[71,58],[60,37],[27,97],[7,56],[56,126],[24,59],[46,76],[15,79],[18,3],[98,8],[110,62],[76,30],[38,63]], "k": 66 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "coordinates": [[21,80],[17,111],[0,126],[20,81],[50,76],[80,32],[7,97],[21,19],[50,91],[58,68],[55,4],[37,56],[20,42],[6,35],[38,72],[96,6],[11,70],[10,91],[11,94],[46,88],[81,64],[37,78],[15,75],[90,79],[13,103],[46,66],[2,95]], "k": 67 }
assert my_solution.countPairs(**test_input) == 26

test_input = { "coordinates": [[65,15],[73,72],[60,97],[101,107],[3,2],[4,20],[90,74],[71,7],[113,95],[39,17],[87,56],[2,76],[27,122],[48,41]], "k": 79 }
assert my_solution.countPairs(**test_input) == 9

test_input = { "coordinates": [[82,41],[27,65],[94,92],[15,82],[56,69],[30,57],[28,28],[5,53],[100,2],[112,44],[23,6],[92,29],[18,69],[124,26],[125,88],[97,54],[7,31],[50,80]], "k": 39 }
assert my_solution.countPairs(**test_input) == 7

test_input = { "coordinates": [[72,31],[86,19],[63,97],[11,118],[8,67],[14,6],[6,69],[51,1],[70,34],[98,68],[84,29],[47,37],[94,75],[73,15],[34,59],[71,42],[45,98],[22,52],[70,94],[67,78],[64,110],[104,5],[65,28],[87,100],[93,10]], "k": 75 }
assert my_solution.countPairs(**test_input) == 10

test_input = { "coordinates": [[90,16],[30,5],[16,71],[21,75],[33,55],[76,76],[16,50],[19,42],[18,59],[30,46],[6,21],[19,73],[35,78],[36,98],[30,77],[6,65],[87,31],[69,46],[62,42],[14,50],[44,29],[86,56]], "k": 17 }
assert my_solution.countPairs(**test_input) == 5

test_input = { "coordinates": [[27,30],[15,52],[26,30],[26,30],[15,53],[75,57],[27,30],[95,67],[26,31],[27,31],[15,53],[90,84],[27,30],[90,85],[10,3],[48,59]], "k": 1 }
assert my_solution.countPairs(**test_input) == 15

test_input = { "coordinates": [[6,12],[53,6],[16,65],[22,42],[66,85]], "k": 54 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "coordinates": [[45,11],[43,19],[35,27],[43,13],[38,28],[41,59],[68,39],[29,47]], "k": 30 }
assert my_solution.countPairs(**test_input) == 5

test_input = { "coordinates": [[39,98],[1,97],[41,90],[1,83],[65,2],[7,27],[79,51],[124,88],[32,97]], "k": 87 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "coordinates": [[54,49],[98,5],[98,25],[75,53],[117,42],[111,6],[31,85],[124,49],[120,115]], "k": 70 }
assert my_solution.countPairs(**test_input) == 4

test_input = { "coordinates": [[33,9],[59,5],[71,12],[36,2],[6,92],[32,81],[45,72],[54,67],[17,83],[64,19],[24,68],[58,56],[69,87],[76,23],[86,14],[40,25],[50,38],[50,71]], "k": 38 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "coordinates": [[7,7],[44,51],[93,41],[43,37],[31,2],[39,52],[12,68],[92,78],[59,78],[95,70],[62,45],[30,79],[7,17],[3,89],[60,35]], "k": 29 }
assert my_solution.countPairs(**test_input) == 6

test_input = { "coordinates": [[77,91],[3,84],[91,18],[83,18],[56,94],[92,19],[69,83],[88,0],[73,95],[65,87],[95,89],[90,90],[19,36],[94,1],[20,18],[14,62],[77,62],[76,92],[14,55],[22,39],[75,95],[94,17],[21,38]], "k": 8 }
assert my_solution.countPairs(**test_input) == 10

test_input = { "coordinates": [[27,49],[44,38],[99,7],[32,33],[60,98],[98,84],[93,89],[85,80]], "k": 95 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "coordinates": [[86,74],[117,67],[106,78],[66,82],[15,75],[76,72],[116,64],[85,51],[109,87],[75,69],[103,89],[80,20],[101,95],[124,76],[91,53],[100,84],[112,108],[45,94],[14,96]], "k": 44 }
assert my_solution.countPairs(**test_input) == 19

test_input = { "coordinates": [[43,81],[53,103],[106,66],[75,67],[88,96],[112,90],[23,87],[26,70],[75,78],[102,100],[82,15],[69,5],[32,106],[38,116],[10,32],[48,46],[7,93],[61,43],[11,38],[4,99],[58,4],[29,10],[28,6],[40,80],[7,110],[95,91],[24,56],[92,53]], "k": 84 }
assert my_solution.countPairs(**test_input) == 19

test_input = { "coordinates": [[28,78],[90,77],[51,40],[67,125],[31,62],[19,116],[3,79],[61,5],[39,7],[27,9],[56,33],[100,69],[30,72],[0,66],[17,54],[123,6],[87,72],[11,25],[24,49],[103,81],[37,58],[26,53],[23,45],[120,1],[39,96],[58,84],[97,5]], "k": 73 }
assert my_solution.countPairs(**test_input) == 17

test_input = { "coordinates": [[63,22],[10,98],[61,3],[7,4],[0,111],[56,17],[50,11],[30,97],[16,2],[59,77],[4,48],[42,94],[63,1],[42,3],[13,9],[27,100],[60,30],[1,34],[54,43],[3,32],[15,60],[39,9],[52,82],[19,7],[42,82],[88,96]], "k": 23 }
assert my_solution.countPairs(**test_input) == 18

test_input = { "coordinates": [[76,84],[58,43],[15,66],[83,35],[38,10],[12,44],[70,34],[20,36],[13,29],[17,24],[53,100]], "k": 61 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "coordinates": [[5,32],[28,98],[26,96],[30,100],[29,101],[32,50],[0,73],[29,101],[65,92],[54,15],[1,36],[68,46],[98,62],[67,90],[28,98],[12,81],[16,83],[55,77],[49,14],[0,12],[25,101],[27,99],[4,47],[19,99],[63,62],[56,92]], "k": 8 }
assert my_solution.countPairs(**test_input) == 18

test_input = { "coordinates": [[95,54],[53,94],[90,47],[89,90],[90,47],[73,36],[73,84],[72,49],[63,91],[39,66],[57,80],[80,59]], "k": 30 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "coordinates": [[66,53],[64,2],[94,55],[85,23],[74,7],[18,83],[32,95],[55,13],[81,34],[25,125],[73,75],[49,32],[57,19],[0,19],[72,79],[65,8],[118,38],[44,44],[68,16],[62,62],[0,116],[60,21]], "k": 57 }
assert my_solution.countPairs(**test_input) == 7

test_input = { "coordinates": [[38,73],[37,117],[95,92],[28,22],[16,64],[53,0],[65,85],[91,16],[82,28],[57,9],[53,75],[47,45],[30,43],[91,47],[56,94],[53,39]], "k": 63 }
assert my_solution.countPairs(**test_input) == 5

test_input = { "coordinates": [[11,11],[96,86],[86,64],[94,11],[121,100],[68,1],[84,54],[21,40],[8,3],[96,44],[96,127],[42,25],[43,119],[94,10],[71,0],[84,96],[79,73],[37,11],[74,15],[4,53],[27,59],[0,67]], "k": 83 }
assert my_solution.countPairs(**test_input) == 13

test_input = { "coordinates": [[0,8],[45,94],[87,72],[12,98],[4,16],[91,88],[26,100],[8,31],[56,89],[13,54],[22,26],[2,18],[7,36],[19,13],[61,72],[44,10],[44,87],[1,38],[25,23],[24,36],[21,50],[27,13],[95,68],[15,13],[54,68],[5,62]], "k": 28 }
assert my_solution.countPairs(**test_input) == 17

test_input = { "coordinates": [[97,95],[100,90],[99,87],[100,80],[102,82],[4,7],[0,69],[99,89]], "k": 10 }
assert my_solution.countPairs(**test_input) == 6

test_input = { "coordinates": [[22,68],[75,70],[67,78]], "k": 95 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "coordinates": [[36,33],[73,78],[41,27],[58,34],[10,67]], "k": 80 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "coordinates": [[2,37],[39,2],[12,57],[33,38],[73,36],[85,22],[9,95],[31,64],[22,3]], "k": 76 }
assert my_solution.countPairs(**test_input) == 4

test_input = { "coordinates": [[44,0],[95,53],[37,6],[40,4],[5,73],[33,2],[16,71],[36,8],[87,50],[31,71],[83,57],[4,31],[35,79],[12,70],[93,55],[21,77],[97,9],[95,53],[10,73],[78,100],[22,48],[87,50],[74,64]], "k": 15 }
assert my_solution.countPairs(**test_input) == 17

test_input = { "coordinates": [[16,39],[17,57],[14,38],[22,62],[69,40],[2,53],[23,63],[20,35],[25,49]], "k": 31 }
assert my_solution.countPairs(**test_input) == 15

test_input = { "coordinates": [[0,46],[13,69],[38,80],[60,17],[72,83],[27,78],[21,9],[9,29],[84,39],[59,117],[79,65],[1,116],[90,71],[53,91],[46,3],[100,73],[105,23],[12,81],[113,84],[111,25],[27,1],[48,49],[51,53],[93,83],[48,29],[27,21],[9,71]], "k": 91 }
assert my_solution.countPairs(**test_input) == 19

test_input = { "coordinates": [[50,93],[12,98],[26,22],[50,19],[20,70],[53,119],[1,127],[38,100],[52,116],[89,71],[9,98],[34,94],[12,98],[29,119],[60,29],[97,81],[102,84],[13,15],[10,28],[40,26],[16,87],[45,83],[55,83],[62,35],[30,94],[7,75],[14,86],[16,12],[73,88],[60,124]], "k": 78 }
assert my_solution.countPairs(**test_input) == 26

test_input = { "coordinates": [[19,26],[2,28],[3,10],[42,61],[56,56]], "k": 23 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "coordinates": [[56,55],[42,83],[35,97],[28,32],[52,76],[34,20],[68,88],[90,38],[99,76],[32,20],[22,85],[50,34],[4,11],[17,92],[59,80],[66,65],[47,60]], "k": 59 }
assert my_solution.countPairs(**test_input) == 6

test_input = { "coordinates": [[87,78],[72,88],[82,69],[88,79],[36,24],[42,15],[66,94],[32,10],[92,71],[46,89],[74,86],[37,23],[61,44],[66,87],[35,17],[91,78],[43,15],[61,75],[62,70],[61,70],[34,7],[85,64],[35,20],[42,22],[41,27],[82,85],[90,89],[41,13]], "k": 16 }
assert my_solution.countPairs(**test_input) == 20

test_input = { "coordinates": [[48,86],[98,33],[46,68],[91,21],[39,73]], "k": 22 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "coordinates": [[71,47],[68,44],[65,45],[97,43],[97,45],[97,45],[71,41],[103,43],[96,20],[99,41],[57,4],[17,77],[68,44],[16,72],[17,75],[64,69],[19,75],[99,41],[2,21],[71,47],[91,4],[57,2]], "k": 6 }
assert my_solution.countPairs(**test_input) == 21

test_input = { "coordinates": [[5,11],[16,87],[48,55],[26,15],[41,58],[12,14],[81,66],[30,5]], "k": 14 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "coordinates": [[85,89],[119,89],[34,16],[54,41],[55,29],[33,34],[54,30],[80,74],[12,92],[42,49],[69,7],[47,13],[26,38],[39,96],[61,58],[24,48],[46,47]], "k": 34 }
assert my_solution.countPairs(**test_input) == 6

test_input = { "coordinates": [[35,45],[58,17],[64,60],[117,23],[18,63],[26,55],[65,54]], "k": 85 }
assert my_solution.countPairs(**test_input) == 4

test_input = { "coordinates": [[60,1],[57,6],[39,3],[58,7],[61,14],[19,80],[46,0],[84,35],[43,3],[46,4],[48,71],[48,75],[85,40],[46,45],[6,20],[35,7],[57,6],[51,78],[68,25],[17,0]], "k": 12 }
assert my_solution.countPairs(**test_input) == 12

test_input = { "coordinates": [[95,0],[36,24],[68,27],[80,14],[39,2],[93,52],[107,52],[86,63],[82,13],[55,14],[8,52],[99,20],[101,36],[50,70],[26,98],[95,41]], "k": 54 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "coordinates": [[43,14],[55,83],[33,89],[44,74],[46,84],[51,87],[61,69],[1,89]], "k": 32 }
assert my_solution.countPairs(**test_input) == 10

test_input = { "coordinates": [[88,15],[93,65],[52,39],[20,24],[100,36],[39,17],[26,77],[52,39],[47,83],[98,99],[43,28],[72,29],[21,48],[43,32],[60,108],[44,47],[45,125],[84,94]], "k": 83 }
assert my_solution.countPairs(**test_input) == 13

test_input = { "coordinates": [[12,2],[43,87],[21,100],[79,63],[5,6],[70,75],[20,55],[23,55],[17,31],[121,89],[27,71],[27,22],[42,34],[15,14],[16,40],[49,68],[30,48],[45,43],[88,23],[47,15],[16,41],[8,5]], "k": 81 }
assert my_solution.countPairs(**test_input) == 8