Problem Statement
Definition
- Class:
- DistantPoints
- Method:
- getKth
- Parameters:
- int, int
- Returns:
- int[]
- Method signature:
- int[] getKth(int N, int K)
- (be sure your method is public)
Notes
- The Euclidean distance between two points (x1,y1) and (x2,y2) is equal to the square root of (x1-x2)^2+(y1-y2)^2.
Constraints
- N will be between 2 and 10, inclusive.
- K will be between 1 and the amount of points inside the square with side length 2^N+2, inclusive.
Examples
4
2
Returns: {17, 17 }
The square stretches from (0,0) to (18,18). After you paint (1,1), the farthest point within the square is (17,17).
4
3
Returns: {1, 17 }
Now there are two candidates. Both upper-left and bottom-right points within the square are equally distant from the already painted two, so we choose the leftmost one.
4
5
Returns: {9, 9 }
After you paint all the corners, the best choice is the center of the square.
3
14
Returns: {1, 3 }
5
1089
Returns: {33, 32 }
2
1
Returns: {1, 1 }
2
2
Returns: {5, 5 }
2
5
Returns: {3, 3 }
2
11
Returns: {2, 4 }
2
18
Returns: {2, 5 }
2
22
Returns: {4, 3 }
2
23
Returns: {4, 5 }
2
25
Returns: {5, 4 }
3
2
Returns: {9, 9 }
3
4
Returns: {9, 1 }
3
9
Returns: {9, 5 }
3
10
Returns: {3, 3 }
3
12
Returns: {7, 3 }
3
21
Returns: {7, 1 }
3
40
Returns: {8, 6 }
3
70
Returns: {7, 4 }
3
76
Returns: {8, 7 }
3
79
Returns: {9, 4 }
4
29
Returns: {3, 15 }
4
41
Returns: {15, 15 }
4
145
Returns: {16, 16 }
4
148
Returns: {1, 6 }
4
201
Returns: {7, 10 }
4
225
Returns: {10, 7 }
4
231
Returns: {11, 2 }
4
266
Returns: {15, 4 }
4
276
Returns: {16, 7 }
4
277
Returns: {16, 9 }
5
1
Returns: {1, 1 }
5
2
Returns: {33, 33 }
5
5
Returns: {17, 17 }
5
16
Returns: {9, 1 }
5
67
Returns: {21, 25 }
5
72
Returns: {25, 29 }
5
190
Returns: {11, 9 }
5
191
Returns: {11, 13 }
5
192
Returns: {11, 17 }
5
196
Returns: {11, 33 }
5
197
Returns: {13, 3 }
5
222
Returns: {19, 1 }
5
233
Returns: {21, 11 }
5
278
Returns: {31, 21 }
5
400
Returns: {14, 30 }
5
402
Returns: {16, 2 }
5
412
Returns: {16, 22 }
5
425
Returns: {18, 16 }
5
434
Returns: {20, 2 }
5
528
Returns: {30, 30 }
5
545
Returns: {32, 32 }
5
546
Returns: {1, 2 }
5
666
Returns: {8, 11 }
5
667
Returns: {8, 13 }
5
999
Returns: {28, 17 }
5
1062
Returns: {32, 11 }
6
8
Returns: {33, 65 }
6
50
Returns: {9, 65 }
6
101
Returns: {21, 29 }
6
202
Returns: {25, 45 }
6
303
Returns: {3, 55 }
6
304
Returns: {3, 59 }
6
307
Returns: {7, 7 }
6
445
Returns: {39, 47 }
6
780
Returns: {29, 15 }
6
999
Returns: {55, 33 }
6
1109
Returns: {2, 40 }
6
1126
Returns: {4, 10 }
6
1569
Returns: {30, 64 }
6
1570
Returns: {32, 2 }
6
1970
Returns: {56, 34 }
6
2969
Returns: {27, 22 }
6
3571
Returns: {45, 56 }
6
4000
Returns: {59, 4 }
6
4204
Returns: {65, 22 }
7
25
Returns: {129, 97 }
7
61
Returns: {65, 49 }
7
152
Returns: {1, 105 }
7
244
Returns: {89, 81 }
7
1000
Returns: {109, 73 }
7
2000
Returns: {115, 59 }
7
2981
Returns: {53, 91 }
7
3493
Returns: {85, 59 }
7
3523
Returns: {87, 49 }
7
7000
Returns: {88, 46 }
8
3
Returns: {1, 257 }
8
301
Returns: {9, 185 }
8
2148
Returns: {5, 17 }
8
2149
Returns: {5, 25 }
8
2223
Returns: {13, 97 }
8
3939
Returns: {225, 45 }
8
10412
Returns: {65, 107 }
8
25555
Returns: {140, 164 }
8
49021
Returns: {125, 124 }
8
50005
Returns: {133, 36 }
8
50505
Returns: {137, 8 }
8
51515
Returns: {144, 229 }
8
55815
Returns: {178, 91 }
8
61814
Returns: {225, 10 }
8
63000
Returns: {234, 69 }
8
66044
Returns: {257, 246 }
8
66049
Returns: {257, 256 }
9
1
Returns: {1, 1 }
9
2
Returns: {513, 513 }
9
4
Returns: {513, 1 }
9
5
Returns: {257, 257 }
9
9
Returns: {513, 257 }
9
123
Returns: {353, 97 }
9
124
Returns: {353, 161 }
9
141
Returns: {481, 225 }
9
821
Returns: {257, 369 }
9
1012
Returns: {449, 145 }
9
1255
Returns: {89, 89 }
9
5287
Returns: {133, 301 }
9
6367
Returns: {269, 237 }
9
9052
Returns: {45, 169 }
9
9929
Returns: {97, 477 }
9
28821
Returns: {383, 79 }
9
30319
Returns: {427, 439 }
9
55152
Returns: {345, 99 }
9
77825
Returns: {92, 512 }
9
77826
Returns: {94, 2 }
9
92571
Returns: {208, 308 }
9
110000
Returns: {344, 350 }
9
120000
Returns: {422, 382 }
9
120212
Returns: {424, 294 }
9
146000
Returns: {57, 102 }
9
168620
Returns: {145, 198 }
9
170636
Returns: {153, 126 }
9
190002
Returns: {228, 383 }
9
242414
Returns: {433, 42 }
9
243491
Returns: {437, 144 }
9
261000
Returns: {505, 278 }
9
261522
Returns: {507, 296 }
9
263111
Returns: {513, 396 }
9
263167
Returns: {513, 508 }
9
263168
Returns: {513, 510 }
9
263169
Returns: {513, 512 }
10
1
Returns: {1, 1 }
10
2
Returns: {1025, 1025 }
10
3
Returns: {1, 1025 }
10
4
Returns: {1025, 1 }
10
5
Returns: {513, 513 }
10
6
Returns: {1, 513 }
10
13
Returns: {769, 769 }
10
24
Returns: {1025, 257 }
10
450
Returns: {673, 33 }
10
3031
Returns: {449, 241 }
10
3960
Returns: {897, 849 }
10
17063
Returns: {29, 301 }
10
29111
Returns: {781, 429 }
10
50000
Returns: {529, 101 }
10
99922
Returns: {531, 323 }
10
100002
Returns: {531, 643 }
10
105627
Returns: {619, 615 }
10
122762
Returns: {887, 547 }
10
192918
Returns: {479, 117 }
10
222192
Returns: {707, 249 }
10
393933
Returns: {512, 408 }
10
449125
Returns: {728, 200 }
10
474998
Returns: {828, 746 }
10
475666
Returns: {832, 34 }
10
478977
Returns: {844, 512 }
10
499494
Returns: {924, 586 }
10
500522
Returns: {928, 594 }
10
501895
Returns: {934, 268 }
10
509959
Returns: {966, 12 }
10
534001
Returns: {17, 976 }
10
600000
Returns: {146, 749 }
10
709259
Returns: {359, 942 }
10
766922
Returns: {472, 443 }
10
778461
Returns: {494, 971 }
10
902512
Returns: {736, 1023 }
10
955612
Returns: {840, 623 }
10
1000000
Returns: {927, 224 }
10
1001012
Returns: {929, 198 }
10
1011202
Returns: {949, 78 }
10
1042494
Returns: {1010, 137 }
10
1050000
Returns: {1024, 799 }
10
1050211
Returns: {1025, 196 }
10
1050585
Returns: {1025, 944 }
10
1050620
Returns: {1025, 1014 }
10
1050625
Returns: {1025, 1024 }