10245 - The Closest Pair Problem

[henrikland]

Hi!

I keep getting TLE, despite implementing the O(n log n) recursive algorithm shown here http://rosettacode.org/wiki/Closest-pair_problem.
I've also tried using 300 sets of 10000 randomly generated points as input, the runtime is then ~5.7 seconds.

Output seems to be correct, so I'm not sure what the problem is. Any tips? Is the test input even larger?

Code: Select all

deleted

Thanks in advance!

Edit: The problem seems to be compiling with the -ansi flag, which prints all results as 0.0000. Submitting as C++ however, yields WA...
Does anyone have another tricky input to test with? I've tested the tricky inputs suggested in this thread, they all give correct output. Any more tricky inputs?

Input:

Code: Select all

2
0 10000
0 0.00001
2
0 10000
0 0.0001
2
0 10000
0 0.0009
2
0 10000
0 0.00009
3
0 0
10000 10000
20000 20000
5
0 2
6 67
43 71
39 107
189 140
1
0 0
3
1 1
1 1
1 1
30
5253 2675
1436 1023
8447 1510
4610 406
538 4362
6299 2192
585 3791
5674 8538
9614 6466
6246 2506
915 4726
4660 411
5722 624
8857 6201
5093 7510
2588 2060
4949 4693
9181 5893
5443 7492
8136 329
4655 4812
9319 8815
4572 1012
3707 6556
1656 3150
520 4729
7037 8659
5251 1017
8617 1775
5644 573
30
647 806
998 945
395 611
641 923
423 625
490 684
327 571
767 821
792 294
963 157
366 960
208 350
142 205
767 467
850 596
251 331
888 270
376 359
153 466
87 930
106 321
702 85
644 860
161 895
228 999
163 471
410 580
43 770
394 800
199 819
30
184 125
253 37
364 470
155 331
233 341
18 322
337 207
237 357
249 51
146 470
308 441
24 227
155 367
375 475
319 119
283 113
329 298
428 258
134 387
58 82
273 263
260 256
177 112
242 410
112 297
318 496
433 204
28 376
341 81
204 217
30
134 154
151 212
48 129
204 61
203 130
58 226
191 41
68 225
234 90
135 146
30 135
177 14
148 24
65 33
150 86
56 52
226 69
215 74
243 178
184 73
60 10
65 113
6 55
20 168
175 212
222 104
16 39
79 201
187 126
133 80
100
283 211
947 1581
1915 1178
571 1753
1392 1459
1138 554
1399 1440
1000 1960
1686 1702
1383 229
1724 524
716 569
617 337
1429 1934
812 768
1119 1643
288 341
253 1456
694 29
1704 1286
97 1503
409 1076
1683 940
327 1185
283 1255
49 285
684 693
682 1869
380 1251
471 538
401 1802
1754 57
1339 772
1181 553
1297 1691
797 655
557 1109
1388 721
1543 641
132 52
578 1553
1964 1125
312 1045
1628 554
391 811
129 694
8 1465
80 1023
1939 38
905 256
133 1227
1331 652
764 1133
1617 873
1160 1527
1624 185
1090 1578
224 567
841 1364
1531 422
1505 1169
1785 762
490 612
183 322
1857 804
907 1884
25 375
241 86
1208 559
786 1013
833 1094
1929 1225
1604 139
1462 1899
1687 410
286 1292
1379 1837
1129 876
1887 613
1769 1756
893 326
1738 389
679 149
1919 1781
407 1427
119 1325
1272 1046
401 1131
1168 940
148 808
842 1151
1245 529
1397 919
1687 1270
815 1042
301 677
1343 452
1023 1428
677 1775
677 880
0
2
412.21 9123.1
31.1 312.4
3
0 0
10000 10000
20000 20000
5
0 2
6 67
43 71
39 107
189 140
2
0.3 1.2
0.7 5.2
90
17392.8 23045.1
24003.2 8249.9
16480.3 31007.4
1728.9 11285.0
11508.3 13965.7
6445.3 8105.0
32962.1 30779.4
5987.1 26761.2
39025.9 10545.0
18942.0 26502.6
8893.0 10155.4
21354.4 12309.0
36084.4 34687.9
27194.0 20945.2
34490.3 25278.9
8324.0 31622.9
39872.8 11883.1
2890.5 32327.2
15247.5 16353.1
1954.0 16254.7
24359.7 26755.8
29170.4 20034.6
18431.0 17321.8
27866.9 6792.8
4930.6 17456.9
27612.3 6808.9
30753.1 13823.6
20146.8 8966.7
29911.9 38472.7
35386.8 7340.8
10598.9 36037.4
7920.6 3710.8
7673.3 10471.7
38460.1 22446.3
38701.0 22920.8
21311.8 12049.3
3719.1 23060.7
12017.8 10482.2
17275.0 22150.1
39607.0 11519.9
29964.0 22205.7
7664.5 27219.3
7821.2 32352.3
30825.0 27811.3
6787.3 9368.4
5405.8 37847.1
13193.1 17386.2
39493.2 13326.4
35772.8 20866.4
15422.4 9588.5
21637.8 34473.8
29169.8 36734.2
18851.7 25357.0
19142.3 12822.8
24342.7 36126.7
29967.6 18749.4
17603.9 14306.7
18294.2 9267.4
37078.7 25425.2
34793.6 9119.2
18601.5 15501.3
32887.5 199.4
25161.1 31794.7
12661.1 32380.7
13604.4 20933.9
27042.9 39718.8
8088.2 6877.5
3869.7 27847.9
12305.9 26939.9
34701.9 23012.0
1761.4 36648.6
22590.5 36304.7
5572.1 19365.4
16425.8 884.7
21639.2 14286.1
29787.4 11219.4
23054.0 240.7
3670.6 34310.1
38326.1 8215.1
784.2 27967.0
27685.8 11930.5
18808.0 39462.4
27310.3 35774.0
34349.2 34312.9
17325.0 39616.3
7900.1 29051.1
25355.8 19086.4
10087.0 2125.9
3010.6 2563.2
28484.5 26512.8
0

My program outputs:

Code: Select all

10000.0000
9999.9999
9999.9991
9999.9999
INFINITY
36.2215
INFINITY
0.0000
50.2494
11.1803
12.0830
8.0623
20.2485

[brianfry713]

http://www.uvatoolkit.com/problemssolve.php

[alireza0xn]

hi all.
my program passed all(maybe most of them! i don't remember) the tests in this topic however i got WA again & again & ...
so what was the problem????

co-vertical & duplicate(special case of co-vertical) points( of course if you use X coordinate to split the points)

e.g.:
input :

6
1 1
1 2
1 3
1 4
1 5
1 6
5
1 15
89 63
1 89
3 2
1 89
0

Expected Output:

1.0000
0.0000

but my program crashed !!! why? because in sorting points by their x coordinate i just had done the following:

Code: Select all

bool XCompare(Point* a , Point*b)
{
  return b->x - a->x > EPS;
}

which should've been changed to this:

Code: Select all

bool XCompare(Point* a , Point*b)
{
  if(ABS(b->x - a->x) <= EPS)
    return b->y - a->y > EPS;
  return b->x - a->x > EPS;
}

which led to RE in my program every time!(i guess because of infinite recursion(left or right set was the same as the original problem) => heap allocation failure)

after u sort the points lexicographically , if there is any (((((((duplicate))))))) point the answer should be 0.0000 (obviously can be checked in O(N) )
if there is no repeated points then u can continue normally

as i said i hadn't thought about co-vertical & duplicate points but i'm almost sure there are some testcases like the one mentioned
because when i did the modifications i got AC! at last (it was making me mad)

i wish it helps someone