849 - Radar Tracking

[Kostya]

Is the simple output for test case 2 correct?

The answer 270.00 83.33 means that we have speed = (83.33-10.00)/2 = 36.66. But this means that the anwer is wrong 'cause the radar will see the object for the second time at 90.0 100.00-36.66*2.

[Adrian Kuegel]

I think it is wrong, too. But perhaps one should assume that the radar observes the object in the same "round" or in the next "round" at this angle. Therefore you should display always two outputs if the observation angles differ.

[Picard]

you are right. the judge's solution algorithm is false.
if you want to get accepted just ignore the possible observations between the two input positions. this always leads to a next "round" solution and if a2>a1 then a same "round" solution too.

[gvcormac]

you are right. the judge's solution algorithm is false.
if you want to get accepted just ignore the possible observations between the two input positions. this always leads to a next "round" solution and if a2>a1 then a same "round" solution too.

The sample output in the problem statement is wrong. It should be:

90.00 120.00
270.00 230.00
199.93 64.96 223.39 130.49

I have sent the correction, along with the official judges' data, to uva. Presumably they will update it in due course.

Unfortunately that means that Picard's submissions will be judged WA. Even the ones that give the correct output (as opposed to the given output) on the sample. UVA was using unofficial test data that didn't check a case that Picard missed.

In the interim, if you'd like to send me your solutions at acm00@plg.uwaterloo.ca,I will let you know whether not they pass the official test cases.

[gvcormac]

I see that the corrected version of Radar Tracking is now posted.

[kep]

I cant understand how there are two solutions for the third case ... The first one is okay, but how is the second one explained ?

[yiuyuho]

how much does tolerances come into play in this problem? I coded this problem using divide and conquer, and I have to use 3 different tolerances so that my own data will run correctly. I am getting WA for the uva judge. Any suggestions on what should be done?

[maweaver]

Does anyone have a hint on how to solve this one? I tried mapping the plane's angle as a function of time, which gives a non-linear function that intersects the radar's angle 0-3 times/sweep. I'm attaching a graph of the first solution of the third sample so you can see what I'm talking about; you can see the intersection at 90 degrees, although the ones at 180 and 199.93 kind of run together.

I tried to use Newton's method to find all roots for each sweep, but I couldn't get a consistently stable answer. Bisection method doesn't really work, since there can be multiple roots. Since this is in the Computational Geometry section of Programming Challenges, I assume their is a more geometrical way that I am missing? I did try plotting the signed triangle area between the plane and a point one unit away in the direction the radar is facing, which is zero when the radar is facing the plane (and also when it is 180 degrees away or the plane is on top of the station), but I just ended up with an even weirder non-linear function.

[maweaver]

After much hair-pulling, finally got AC. I have my doubts that the judge is correct though. For example, consider the input '285.10 697.47 88.60 288.07'. The AC solution is '96.85 971.19 98.96 2496.18', but I think the second of these is not valid. For the third intercept to be at 98.96, the first would have to be at 285.10 of the first sweep and the second at 88.60 of the second sweep. If that were the case though, there would have been another interception at 49.32 degrees on the second sweep, so the solution is not valid. Excluding it gives WA though

In any case, for others stuck, here are some sample tests and their AC solutions:

In:

Code: Select all

90.0 100.0 90.0 110.0
90.0 100.0 270.0 10.0
90.0 100.0 180.0 50.0
88.597 697.474 285.103 288.068
285.103 697.474 88.597 288.068
286.164 308.873 6.389 860.262
6.389 308.873 286.164 860.262
284.618 801.905 114.784 934.587
114.784 801.905 284.618 934.587
187.074 673.915 129.657 459.365
129.657 673.915 187.074 459.365
102.179 884.098 281.092 387.536
281.092 884.098 102.179 387.536
333.225 7.844 97.936 973.014
97.936 7.844 333.225 973.014
95.664 228.706 34.465 554.046
34.465 228.706 95.664 554.046
14.197 964.855 278.614 48.567
278.614 964.855 14.197 48.567
7.22 266.87 290.601 289.451
290.601 266.87 7.22 289.451
318.461 938.592 71.214 829.09
71.214 938.592 318.461 829.09
249.65 122.39 294.165 345.078
294.165 122.39 249.65 345.078
294.908 494.923 280.267 540.694
280.267 494.923 294.908 540.694
215.201 936.249 73.482 504.213
73.482 936.249 215.201 504.213
262.005 723.785 313.609 291.659
313.609 723.785 262.005 291.659
77.086 73.208 280.246 351.013
280.246 73.208 77.086 351.013
31.393 924.441 131.802 608.549
131.802 924.441 31.393 608.549
344.119 255.575 207.238 194.493
207.238 255.575 344.119 194.493
196.894 677.612 10.892 908.206
10.892 677.612 196.894 908.206
114.521 141.897 35.185 304.906
35.185 141.897 114.521 304.906
319.829 228.302 174.224 969.424
174.224 228.302 319.829 969.424
83.886 151.868 317.786 610.362
317.786 151.868 83.886 610.362
174.321 760.003 244.279 465.834
244.279 760.003 174.321 465.834
245.533 10.706 0.912 267.85
0.912 10.706 245.533 267.85
190.698 233.895 218.837 208.532
218.837 233.895 190.698 208.532
110.699 885.055 120.542 882.229
120.542 885.055 110.699 882.229
247.922 57.438 166.441 360.309
166.441 57.438 247.922 360.309
293.226 198.684 205.685 462.932
205.685 198.684 293.226 462.932
50.526 70.594 6.663 670.226
6.663 70.594 50.526 670.226
40.544 455.507 288.285 304.815
288.285 455.507 40.544 304.815
239.101 93.365 66.65 934.095
66.65 93.365 239.101 934.095
100.846 333.408 152.767 675.39
152.767 333.408 100.846 675.39
306.181 255.536 63.36 242.781
63.36 255.536 306.181 242.781
268.769 552.532 194.956 7.87
194.956 552.532 268.769 7.87
48.022 943.595 50.711 763.557
50.711 943.595 48.022 763.557
10.414 511.196 306.358 820.531
306.358 511.196 10.414 820.531
73.414 292.199 23.395 709.307
23.395 292.199 73.414 709.307
79.973 4.682 242.592 405.739
242.592 4.682 79.973 405.739
163.111 889.248 273.298 508.267
273.298 889.248 163.111 508.267
133.812 488.893 217.129 16.271
217.129 488.893 133.812 16.271
265.103 620.449 303.915 54.48
303.915 620.449 265.103 54.48
302.311 612.632 190.198 596.198
190.198 612.632 302.311 596.198
238.727 536.717 195.512 68.71
195.512 536.717 238.727 68.71
45.483 996.616 226.106 944.169
226.106 996.616 45.483 944.169
87.636 193.756 199.496 907.862
199.496 193.756 87.636 907.862
132.134 593.784 186.229 522.506
186.229 593.784 132.134 522.506
106.755 629.362 352.453 672.687
352.453 629.362 106.755 672.687
139.653 178.831 333.633 605.145
333.633 178.831 139.653 605.145
328.129 121.827 345.834 185.825
345.834 121.827 328.129 185.825
21.181 967.825 134.641 247.006
134.641 967.825 21.181 247.006
114.309 84.483 254.78 398.328
254.78 84.483 114.309 398.328
16.193 417.022 18.717 732.654
18.717 417.022 16.193 732.654
220.838 267.747 126.651 998.539
126.651 267.747 220.838 998.539
357.114 836.35 356.762 740.922
356.762 836.35 357.114 740.922
281.748 448.823 79.947 529.151
79.947 448.823 281.748 529.151
32.442 16.233 90.087 334.648
90.087 16.233 32.442 334.648
38.51 482.457 308.072 408.81
308.072 482.457 38.51 408.81
41.356 499.518 83.452 905.601
83.452 499.518 41.356 905.601
229.967 682.847 118.931 82.61
118.931 682.847 229.967 82.61
213.934 593.757 132.473 481.295
132.473 593.757 213.934 481.295
82.501 379.08 9.287 561.467
9.287 379.08 82.501 561.467
43.106 623.43 7.663 89.289
7.663 623.43 43.106 89.289
197.856 53.66 350.826 477.165
350.826 53.66 197.856 477.165
17.577 972.975 330.411 289.044
330.411 972.975 17.577 289.044
5.934 600.056 261.851 321.919
261.851 600.056 5.934 321.919
87.158 362.626 267.066 969.513
267.066 362.626 87.158 969.513
46.775 601.001 17.69 179.282
17.69 601.001 46.775 179.282
314.42 165.327 331.185 759.647
331.185 165.327 314.42 759.647
294.716 159.213 125.816 598.853
125.816 159.213 294.716 598.853
95.824 718.862 195.321 510.481
195.321 718.862 95.824 510.481
330.721 924.496 248.309 973.502
248.309 924.496 330.721 973.502
40.929 437.823 98.86 200.877
98.86 437.823 40.929 200.877
255.953 730.285 316.252 402.239
316.252 730.285 255.953 402.239
175.382 37.832 167.744 997.58
167.744 37.832 175.382 997.58
358.011 988.341 303.682 364.185
303.682 988.341 358.011 364.185
5.702 996.603 139.685 991.338
139.685 996.603 5.702 991.338
180.821 293.814 256.017 292.514
256.017 293.814 180.821 292.514
44.117 877.067 145.855 98.435
145.855 877.067 44.117 98.435
321.09 240.66 66.721 914.386
66.721 240.66 321.09 914.386
80.621 377.522 296.886 580.224
296.886 377.522 80.621 580.224
165.728 891.294 220.196 743.381
220.196 891.294 165.728 743.381
277.77 888.515 37.807 659.8
37.807 888.515 277.77 659.8
299.426 446.193 35.395 721.757
35.395 446.193 299.426 721.757
225.789 193.617 153.045 469.173
153.045 193.617 225.789 469.173
167.145 310.155 176.9 494.055
176.9 310.155 167.145 494.055
284.524 976.893 111.315 421.967
111.315 976.893 284.524 421.967
289.216 197.768 155.363 445.648
155.363 197.768 289.216 445.648
248.042 578.638 199.991 56.547
199.991 578.638 248.042 56.547
9.884 378.636 168.275 146.75
168.275 378.636 9.884 146.75
41.05 776.459 257.244 237.579
257.244 776.459 41.05 237.579
159.36 954.629 201.795 63.61
201.795 954.629 159.36 63.61
226.758 713.399 44.042 516.489
44.042 713.399 226.758 516.489
132.612 264.88 319.666 788.643
319.666 264.88 132.612 788.643
36.058 148.079 202.873 896.419
202.873 148.079 36.058 896.419
275.039 728.549 164.282 356.733
164.282 728.549 275.039 356.733
272.554 274.899 83.55 311.922
83.55 274.899 272.554 311.922
353.765 191.63 280.129 883.987
280.129 191.63 353.765 883.987
53.001 353.299 43.54 769.869
43.54 353.299 53.001 769.869
285.789 30.966 306.031 115.624
306.031 30.966 285.789 115.624
326.931 185.693 193.942 117.384
193.942 185.693 326.931 117.384
35.266 342.35 123.053 295.019
123.053 342.35 35.266 295.019

Out:

Code: Select all

90.00 120.00
270.00 230.00
199.93 64.96 223.39 130.49
275.06 2023.03
96.85 971.19 98.96 2496.18
15.82 1559.24 23.47 4872.02
274.68 1904.69
111.14 4173.48
287.24 2116.66 288.37 4636.74
83.20 811.83
217.85 594.85 231.96 780.45
281.61 1238.17 281.75 2950.79
101.52 2910.81
98.22 3796.93
333.00 2467.66
22.18 1095.67
106.24 960.88 116.27 3541.13
199.70 1040.21
92.33 802.08
261.95 633.20
32.25 541.07 49.78 2016.95
92.51 1921.86 102.38 5802.21
292.84 2707.45
301.83 584.62 310.19 2624.89
241.05 639.42
268.45 616.09
306.56 614.70 352.04 4243.25
53.12 2594.36
232.09 1499.75 237.33 4151.34
32.06 616.74 42.44 976.71
187.49 544.91
277.58 1087.96
79.98 1320.59
163.17 1484.83 176.26 5229.34
355.64 1943.61
188.27 821.52
5.30 1346.55 359.42 500.02
12.28 1979.49 12.90 4202.43
194.92 3955.86
20.35 669.92
126.84 553.81 136.71 1778.95
169.99 2898.60
322.77 1802.92 324.60 3883.45
311.44 1678.80
88.52 1139.06 91.57 2675.02
270.59 605.81 289.88 942.70
126.13 1029.86
2.46 1121.96
244.32 667.58
243.52 231.71 246.42 237.85
163.04 238.01
130.16 905.14 199.33 6875.96
101.07 905.19
161.33 811.80
252.04 652.15 255.42 1963.79
192.05 1070.77
304.32 855.69 312.71 2580.43
4.35 1372.07
52.58 1226.22 54.52 5823.88
257.47 1093.47
66.93 776.21 77.34 2487.74
66.19 2902.30
239.58 3080.23
164.93 1125.09 177.84 4592.34
87.07 1238.94
82.22 558.20 91.07 1617.73
283.14 805.95
90.44 489.32
13.61 779.71
55.07 585.43 215.83 10582.82
43.72 587.02
287.02 1597.77
27.24 1411.34 42.58 5286.21
12.39 1320.79
83.13 1196.75 93.42 4971.77
242.73 1314.19
79.85 1153.65
303.61 1372.62 314.46 4616.86
128.41 1909.25
310.20 543.20
41.01 469.48
80.67 2000.17
132.94 372.16
166.06 1880.86
322.21 1341.65 331.93 3991.03
73.37 325.90
7.90 1417.03 263.45 53.88
225.85 4809.52
45.67 2240.16 45.74 4841.94
204.27 1671.25 207.64 4175.37
81.29 2318.79
219.83 826.17 249.61 4210.58
96.35 871.79
330.47 2107.74
124.65 1486.99 133.66 4290.82
331.40 2042.85
141.14 1140.66 142.00 2306.56
11.15 1885.34 353.93 256.37
319.72 260.29
163.73 468.20 178.56 1091.88
334.15 1540.13
257.82 735.58 259.76 1608.68
109.97 1152.54
19.72 1047.52 21.99 46294.54
15.19 1050.19
118.09 2371.01
227.59 1833.37 232.70 5127.66
356.31 645.56
173.98 47271.34 357.57 645.50
85.56 1202.27 88.03 2757.35
274.15 2200.24
92.16 2383.58
31.15 721.54
275.30 1081.78
67.07 870.56 82.25 3114.93
95.94 1435.08 111.32 6600.17
27.59 1532.25
60.78 909.63
281.54 377.88
96.43 1160.70
246.06 980.69 264.16 3847.14
347.92 1176.02
100.84 1007.37 115.61 3567.55
238.63 331.22
89.07 58.45 180.68 2080.25
352.75 1720.18
196.11 1386.23
237.67 610.26
116.83 815.38 126.71 1747.45
223.07 1166.37
40.44 873.36 52.54 3129.16
267.08 3635.29
87.14 3632.29
267.35 235.07
171.44 442.44 183.26 1991.22
333.15 1338.15 335.47 13865.07
312.37 1387.66
124.18 2015.67
296.41 2216.83
225.27 1205.28 238.52 4197.31
61.47 1570.83
219.51 2270.06
11.79 6787.86 355.66 1890.69
164.82 414.06 168.94 477.37
336.06 400.38
7.00 689.41 11.02 766.37
200.47 782.26
167.60 1978.08
175.53 1938.10 175.68 46286.48
226.42 761.44
78.80 865.34 87.34 1320.32
153.15 2328.07 159.11 6106.19
348.64 3708.83
283.50 547.98 302.30 2123.37
149.71 634.92
208.96 597.24
337.07 1057.81
72.90 1694.29 77.31 4425.18
313.05 2291.84
286.70 2043.31
88.19 1236.51 92.00 2923.41
224.57 763.73 256.05 1182.76
127.79 1243.74
59.49 1655.19 68.28 4934.27
251.79 2444.28
50.49 1402.03 60.48 4200.20
280.92 1808.78
140.03 992.00
236.70 837.22 246.03 2793.86
181.26 681.66 191.53 7988.00
162.69 687.37
107.22 3082.11
287.81 1372.63 288.67 3357.27
146.05 1367.20
296.09 884.87 300.07 2097.55
79.19 384.17
13.69 1384.78
179.48 513.71 182.24 1364.66
356.46 1032.38
232.98 1732.69
62.32 956.72 66.75 2835.94
335.74 2823.72
28.72 613.10
45.01 1342.43 45.35 3022.16
225.46 2930.14
318.39 2805.90
133.45 1500.75 133.92 2986.16
204.20 3151.25
34.79 2829.42
126.87 1451.20
308.21 1039.81 318.74 3593.94
85.92 710.68 86.92 1554.43
269.27 1415.38
273.35 1921.19
4.13 5142.39 359.36 1591.31
40.72 1200.68
55.76 1184.97 60.50 17285.41
308.98 198.52 312.61 1694.53
282.67 206.86
171.14 520.51
345.83 322.29 352.45 913.90
151.88 616.06 167.74 2242.36
2.30 755.19

Just for funs, here are the answers that I believe are actually correct, but that will not give AC:

Code: Select all

90.00 120.00
270.00 230.00
199.93 64.96 223.39 130.49
275.06 2023.03
96.85 971.19
15.82 1559.24 23.47 4872.02
274.68 1904.69
111.14 4173.48
287.24 2116.66
83.20 811.83
217.85 594.85 231.96 780.45
281.61 1238.17
101.52 2910.81
98.22 3796.93
333.00 2467.66
22.18 1095.67
106.24 960.88 116.27 3541.13
199.70 1040.21
92.33 802.08
261.95 633.20
32.25 541.07
92.51 1921.86
292.84 2707.45
301.83 584.62 310.19 2624.89
241.05 639.42
268.45 616.09
306.56 614.70 352.04 4243.25
53.12 2594.36
232.09 1499.75
32.06 616.74 42.44 976.71
187.49 544.91
277.58 1087.96

163.17 1484.83
355.64 1943.61
188.27 821.52
359.42 500.02
12.28 1979.49
194.92 3955.86
20.35 669.92
126.84 553.81 136.71 1778.95
169.99 2898.60
322.77 1802.92
311.44 1678.80
88.52 1139.06 91.57 2675.02
270.59 605.81 289.88 942.70
126.13 1029.86
2.46 1121.96
244.32 667.58
243.52 231.71 246.42 237.85
163.04 238.01
130.16 905.14
101.07 905.19
161.33 811.80
252.04 652.15 255.42 1963.79
192.05 1070.77
304.32 855.69 312.71 2580.43
4.35 1372.07
52.58 1226.22 54.52 5823.88
257.47 1093.47
66.93 776.21
66.19 2902.30

164.93 1125.09 177.84 4592.34
87.07 1238.94
82.22 558.20
283.14 805.95
90.44 489.32
13.61 779.71
55.07 585.43 215.83 10582.82
43.72 587.02
287.02 1597.77
27.24 1411.34 42.58 5286.21
12.39 1320.79
83.13 1196.75 93.42 4971.77
242.73 1314.19
79.85 1153.65
303.61 1372.62
128.41 1909.25
310.20 543.20
41.01 469.48
80.67 2000.17
132.94 372.16
166.06 1880.86
322.21 1341.65
73.37 325.90
7.90 1417.03 263.45 53.88
225.85 4809.52
45.67 2240.16
204.27 1671.25 207.64 4175.37
81.29 2318.79
219.83 826.17
96.35 871.79
330.47 2107.74
124.65 1486.99
331.40 2042.85
141.14 1140.66
11.15 1885.34 353.93 256.37
319.72 260.29
163.73 468.20 178.56 1091.88
334.15 1540.13
257.82 735.58 259.76 1608.68
109.97 1152.54
19.72 1047.52 21.99 46294.54
15.19 1050.19
118.09 2371.01
227.59 1833.37 232.70 5127.66
356.31 645.56
173.98 47271.34 357.57 645.50
85.56 1202.27
274.15 2200.24
92.16 2383.58
31.15 721.54
275.30 1081.78
67.07 870.56
95.94 1435.08 111.32 6600.17
27.59 1532.25
60.78 909.63
281.54 377.88
96.43 1160.70
246.06 980.69
347.92 1176.02
100.84 1007.37 115.61 3567.55
238.63 331.22
89.07 58.45 180.68 2080.25
352.75 1720.18
196.11 1386.23
237.67 610.26
116.83 815.38 126.71 1747.45
223.07 1166.37
40.44 873.36
267.08 3635.29
87.14 3632.29
267.35 235.07
171.44 442.44 183.26 1991.22
333.15 1338.15 335.47 13865.07
312.37 1387.66
124.18 2015.67

225.27 1205.28
61.47 1570.83
219.51 2270.06
355.66 1890.69
164.82 414.06 168.94 477.37
336.06 400.38
7.00 689.41 11.02 766.37
200.47 782.26
167.60 1978.08
175.53 1938.10 175.68 46286.48
226.42 761.44
78.80 865.34 87.34 1320.32
153.15 2328.07
348.64 3708.83
283.50 547.98
149.71 634.92
208.96 597.24
337.07 1057.81
72.90 1694.29 77.31 4425.18
313.05 2291.84
286.70 2043.31
88.19 1236.51
224.57 763.73 256.05 1182.76
127.79 1243.74
59.49 1655.19
251.79 2444.28
50.49 1402.03
280.92 1808.78
140.03 992.00
236.70 837.22 246.03 2793.86
181.26 681.66 191.53 7988.00
162.69 687.37
107.22 3082.11
287.81 1372.63
146.05 1367.20
296.09 884.87
79.19 384.17
13.69 1384.78
179.48 513.71
356.46 1032.38
232.98 1732.69
62.32 956.72
335.74 2823.72
28.72 613.10
45.01 1342.43
225.46 2930.14
318.39 2805.90
133.45 1500.75

34.79 2829.42
126.87 1451.20
308.21 1039.81
85.92 710.68
269.27 1415.38
273.35 1921.19
4.13 5142.39 359.36 1591.31
40.72 1200.68
55.76 1184.97 60.50 17285.41
308.98 198.52 312.61 1694.53
282.67 206.86
171.14 520.51
345.83 322.29
151.88 616.06
2.30 755.19

[gogolyna]

What is the margin of error for police radar guns? I am also curious to know if police radar guns are still accurate in inclement weather such as heavy rain. Does it also matter if you are driving toward the source of the radar or away from it?

[metaphysis]

I got AC. yeah!