$24
Week 3 Programming Assignment Solution
Select your language (C/C++/Java/Python2/Python3)
Paste your code into the submission window.
There are some public test cases and some (hidden) private testcases. "Compile and run" will evaluate your submission against the public test cases.
"Submit" will evaluate your submission against the hidden private test cases and report a score on 100. There are 20 private testcases in all, each with equal weightage. You will only get a score on 100. You will not get feedback on which private testcases passed or failed. Ignore warnings about "Presentation errors".
Prisoner Escape
(Baltic Olympiad in Informatics, 2009)
A group of war prisoners are trying to escape from a prison. They have thoroughly planned the escape from the prison itself, and after that they hope to find shelter in a nearby village. However, the village (marked as B, see picture below) and the prison (marked as A) are separated by a canyon which is also guarded by soldiers. These soldiers sit in their pickets and rarely walk; the range of view of each soldier is limited to exactly 100 meters. Thus, depending on the locations of soldiers, it may be possible to pass the canyon safely, keeping the distance to the closest soldier strictly larger than 100 meters at any moment.
You are to write a program which given the width and the length of the
https://onlinecourses.nptel.ac.in/noc19_cs11/progassignment?name=102 1/29
canyon and the coordinates of every soldier in the canyon, and assuming that soldiers do not change their locations, determines whether prisoners can pass the canyon unnoticed.
Solution Hint
The soldiers can be modelled as an undirected graph G. Let each soldier be represented by a vertex. Add an edge between two vertices if and only if the range of view of the corresponding soldiers overlaps. Add two additional vertices s and t, representing the northern and southern side of the canyon, respectively. Connect s and t to those vertices representing soldiers who range of view includes the respective side of the canyon. Use depth-first-search or breadth-first-search to check whether there is a path between s and t in G.
Input format
The first line contains three integers L, W, and N – the length and the width of the canyon, and the number of soldiers, respectively. Each of the following N lines contains a pair of integers Xi and Yi – the coordinates of i-th soldier in the canyon (0 ≤ Xi ≤ L, 0 ≤ Yi ≤ W). The coordinates are given in meters, relative to the canyon: the southwestern corner of the canyon has coordinates (0, 0), and the northeastern corner of the canyon has coordinates (L,W), as seen in the picture above. Note that passing the canyon may start at coordinate (0,ys) for any 0 ≤ ys ≤ W and end at coordinate (L,ye) for any 0 &\le; ye ≤ W. Neither ys nor ye need to be integer.
Output format
Output a single integer: 0 if the prisoners can escape, 1 if they cannot.
Test data
1 ≤ W ≤ 50,000; 1 ≤ L ≤ 50,000; 1 ≤ N ≤ 250.
Example
Sample input 1
130 340 5
50
130
170
0 180
260
Sample output 1
1
Sample input 2
500 300 4 2/29
300
150
150
Sample output 2
0
Sample Test Cases
Test Case 1
Test Case 2
Test Case 3
Test Case 4
Test Case 5
Test Case 6
Test Case 7
Input
130 340 5
50
130
170
0 180
260
300 6
0
150
300
0
150
300
300 5
0
150
300
150
150
300 4
0
300
150
150
300 5
25
25
275
120
275
300 6
0
300
150
150
300
300
2000 500 31
50
250
350
400
Output
1
1
1
0
0
1
1
400 100
400 200
400 250
400 350
700 50
700 100
700 350
700 400
1000 0
1000 100
1000 150
1000 250
1000 400
1300 200
1600 200
1600 250
1600 300
1600 350
1600 400
1600 450
1900 0
1900 100
1900 150
1900 200
1900 300
1900 400
1900 450
Test Case 8
2000 500
35
1
100 0
100 200
100 250
100 450
400 0
400 50
400 200
400 400
400 450
700 0
700 50
700 200
700 250
700 350
700 400
1000 50
1000 200
1000 450
1300 50
1300 150
1300 250
1600 0
1600 50
1600 100
1600 150
1600 200
1600 250
1600 300
1600 350
1600 400
1600 450
1900 0
1900 300
1900 350
1900 400
2000 500 12
100 200
100 350
400 0
400 150
700 400
Test Case 9
1000 0
0
1000 350
1300 0
1300 100
1600 150
1600 200
1900 400
2000 500 26
100 0
100 50
100 100
100 250
400 0
400 150
400 250
400 350
400 400
700 200
700 250
700 300
Test Case 10
1000 50
1
1000 150
1000 300
1300 200
1300 300
1600 0
1600 250
1600 350
1600 450
1900 0
1900 50
1900 200
1900 250
1900 350
Test Case 11
2000 500 16
0
100 0
100 200
100 300
400 0
Test Case 12
Test Case 13
Test Case 14
400 200
400 300
700 100
1000 0
1000 200
1300 0
1300 200
1300 300
1600 0
1600 200
1600 300
1900 100
500 2000 10
250 100
250 300
250 500
250 700
250 900
1
250 1100
250 1300
250 1500
250 1700
250 1900
500 2000 19
250 100
250 200
350 300
350 400
150 500
300 600
300 700
150 800
100 900
0
250 1000
150 1100
250 1200
150 1300
400 1400
100 1500
100 1600
250 1700
100 1800
200 1900
500 2000 42
1
200 0
200 100
200 200
200 300
200 400
200 500
200 600
200 700
200 800
200 900
200 1000
200 1100
200 1200
200 1300
200 1400
200 1500
200 1600
200 1700
200 1800
200 1900
200 2000
300 0
300 100
300 200
300 300
300 400
300 500
300 600
300 700
300 800
300 900
300 1000
300 1100
300 1200
300 1300
300 1400
300 1500
300 1600
300 1700
300 1800
300 1900
300 2000
Test Case 15
500 2000
41
1
200 0
200 100
200 200
200 300
200 400
200 500
200 600
200 700
200 800
200 900
200 1100
200 1200
200 1300
200 1400
200 1500
200 1600
200 1700
200 1800
200 1900
200 2000
300 0
300 100
300 200
300 300
300 400
300 500
300 600
300 700
300 800
300 900
300 1100
300 1200
300 1300
300 1400
300 1500
300 1600
300 1700
300 1800
300 1900
300 2000
250 1000
500 2000 33
90 0
343 0
117 0
202 200
242 200
394 200
27 400
322 400
323 400
470 600
55 600
182 600
500 800
220 800
83 800
393 1000
Test Case 16 0
87 1000
278 1000
242 1200
347 1200
221 1200
376 1400
85 1400
468 1400
400 1600
270 1600
496 1600
208 1800
265 1800
449 1800
232 2000
485 2000
99 2000
Test Case 17
600 1330 21
1
100 90
100 280
100 470
100 660
100 770
100 880
100 990
100 1100
100 1210
100 1320
470 1270
470 1080
470 890
470 700
470 590
470 480
470 370
470 260
470 150
470 40
285 680
Test Case 18
1000 1000 49
1
0 0
0 100
0 400
0 600
0 700
100 100
100 200
100 400
100 500
100 700
100 900
200 0
200 600
200 700
200 900
300 0
300 400
300 500
300 700
300 800
300 900
400 0
400 100
400 300
400 700
400 800
500 200
500 300
500 400
500 600
500 700
500 800
500 900
600 100
700 100
700 200
700 500
800 0
800 500
800 600
800 700
800 800
800 900
900 100
900 200
900 300
900 400
900 500
900 700
Test Case 19 1000 1000 68 1
100 100
100 200
100 300
100 400
100 500
100 700
100 800
100 900
100 1000
200 300
200 400
200 600
200 900
200 1000
300 100
300 300
300 400
300 600
300 700
300 900
300 1000
400 100
400 200
400 400
400 500
400 600
400 800
500 0
500 100
500 300
500 500
500 600
500 700
500 800
500 900
600 0
600 100
600 200
600 300
600 400
600 500
600 600
600 900
700 0
700 200
700 300
700 600
700 700
700 800
700 900
800 0
800 200
800 300
800 400
800 600
800 700
800 800
800 900
800 1000
900 0
900 100
900 400
900 500
900 600
900 700
900 800
900 900
900 1000
Test Case 20 1000 1000 81 0
100 0
100 100
100 200
100 300
100 400
100 700
100 800
100 900
100 1000
200 0
200 100
200 200
200 300
200 400
200 700
200 800
200 900
200 1000
300 0
300 100
300 200
300 300
300 400
300 700
300 800
300 900
300 1000
400 0
400 100
400 200
400 300
400 400
400 700
400 800
400 900
400 1000
500 0
500 100
500 200
500 300
500 400
500 700
500 800
500 900
500 1000
600 0
600 100
600 200
600 300
600 400
600 700
600 800
600 900
600 1000
700 0
700 100
700 200
700 300
700 400
700 700
700 800
700 900
700 1000
800 0
800 100
800 200
800 300
800 400
800 700
800 800
800 900
800 1000
900 0
900 100
900 200
900 300
900 400
900 700
900 800
900 900
900 1000
1000 1000 42
100 0
100 300
100 500
100 800
100 900
200 200
200 300
200 600
200 800
200 900
200 1000
300 0
300 600
400 0
400 300
400 700
400 1000
500 0
500 100
500 500
Test Case 21
500 800
0
500 1000
600 200
600 400
600 700
600 800
600 1000
700 0
700 100
700 300
700 600
700 700
700 900
700 1000
800 0
800 200
800 300
800 700
800 800
900 0
900 100
900 600
Test Case 22
1000 1000 98
1
100 0
100 100
100 200
100 300
100 400
100 500
100 600
100 700
100 800
100 900
100 1000
200 0
200 100
200 200
200 300
200 400
200 500
200 600
200 700
200 800
200 900
200 1000
300 0
300 100
300 200
300 300
300 400
300 500
300 600
300 700
300 800
300 900
300 1000
400 0
400 100
400 200
400 300
400 400
400 500
400 600
400 700
400 800
400 900
400 1000
500 0
500 100
500 200
500 300
500 400
500 600
500 700
500 800
500 900
500 1000
600 0
600 100
600 200
600 300
600 400
600 500
600 600
600 700
600 800
600 900
600 1000
700 0
700 100
700 200
700 300
700 400
700 500
700 600
700 700
700 800
700 900
700 1000
800 0
800 100
800 200
800 300
800 400
800 500
800 600
800 700
800 800
800 900
800 1000
900 0
900 100
900 200
900 300
900 400
900 500
900 600
900 700
900 800
900 900
900 1000
Test Case 23 600 1330 21 1
100 90
100 280
100 470
100 660
100 770
100 880
100 990
100 1100
100 1210
100 1320
470 1270
470 1080
470 890
470 700
470 590
470 480
470 370
470 260
470 150
470 40
285 680
Test Case 24
3000 1500 200
0
13 1475
113 1475
213 1475
313 1475
413 1475
513 1475
613 1475
903 279
903 379
903 479
903 579
903 679
903 779
903 879
903 979
903 1079
903 1179
903 1279
1105 797
1205 797
1305 797
1405 797
1505 797
1605 797
1705 797
510 6
510 106
510 206
510 306
510 406
510 506
510 606
510 706
510 806
1496 758
1596 758
1696 758
1796 758
1896 758
1996 758
2096 758
2196 758
2296 758
2548 43
2548 143
2548 243
2548 343
2548 443
2548 543
2548 643
2548 743
1780 551
1880 551
1980 551
2080 551
2180 551
2280 551
2380 551
2480 551
1894 684
1894 784
1894 884
1894 984
1894 1084
1894 1184
1894 1284
725 1229
825 1229
925 1229
1025 1229
1125 1229
1225 1229
1325 1229
235 354
235 454
235 554
235 654
235 754
235 854
235 954
235 1054
235 1154
235 1254
1435 817
1535 817
1635 817
1735 817
1835 817
1935 817
2035 817
2135 817
276 399
276 499
276 599
276 699
276 799
276 899
276 999
276 1099
276 1199
1345 647
1445 647
1545 647
1645 647
1745 647
1845 647
1945 647
2045 647
2145 647
2245 647
2345 647
2929 336
2929 436
2929 536
2929 636
2929 736
2929 836
2929 936
2929 1036
2929 1136
2929 1236
2929 1336
1370 436
1470 436
1570 436
1670 436
1770 436
1870 436
1970 436
2070 436
2870 435
2870 535
2870 635
2870 735
2870 835
2870 935
2870 1035
2870 1135
2870 1235
1706 871
1806 871
1906 871
2006 871
2106 871
2206 871
2306 871
2406 871
2506 871
2606 871
2407 432
2407 532
2407 632
2407 732
2407 832
2407 932
2407 1032
1000 1289
1100 1289
1200 1289
1300 1289
1400 1289
1500 1289
1600 1289
1195 163
1195 263
1195 363
1195 463
1195 563
1195 663
1195 763
1631 141
1731 141
1831 141
1931 141
2031 141
2131 141
2231 141
2331 141
2431 141
2531 141
2631 141
840 309
840 409
840 509
840 609
840 709
840 809
1896 791
1996 791
2096 791
2196 791
2296 791
2396 791
2496 791
2596 791
2696 791
2796 791
2896 791
437 160
437 260
Test Case 25
3000 1500 200
1
1056 1471
1156 1471
1256 1471
1356 1471
1456 1471
1556 1471
1656 1471
1756 1471
2896 603
2896 703
2896 803
2896 903
2896 1003
2896 1103
2896 1203
947 370
1047 370
1147 370
1247 370
1347 370
1447 370
1547 370
1647 370
1747 370
1847 370
1947 370
1210 696
1210 796
1210 896
1210 996
1210 1096
1210 1196
1161 45
1261 45
1361 45
1461 45
1561 45
1661 45
1761 45
1861 45
1961 45
2061 45
2617 565
2617 665
2617 765
2617 865
2617 965
2617 1065
2617 1165
2617 1265
2617 1365
2617 1465
1571 1435
1671 1435
1771 1435
1871 1435
1971 1435
2071 1435
2171 1435
2271 1435
2371 1435
2471 1435
2055 455
2055 555
2055 655
2055 755
2055 855
2055 955
2055 1055
2055 1155
750 241
850 241
950 241
1050 241
1150 241
1250 241
1350 241
1450 241
1550 241
1650 241
2884 320
2884 420
2884 520
2884 620
2884 720
2884 820
2884 920
2884 1020
2884 1120
2884 1220
2884 1320
1307 1017
1407 1017
1507 1017
1607 1017
1707 1017
1807 1017
520 615
520 715
520 815
520 915
520 1015
520 1115
341 4
441 4
541 4
641 4
741 4
841 4
941 4
1041 4
265 513
265 613
265 713
265 813
265 913
265 1013
265 1113
265 1213
265 1313
265 1413
620 550
720 550
820 550
920 550
1020 550
1120 550
1220 550
2093 357
2093 457
2093 557
2093 657
2093 757
2093 857
2093 957
2093 1057
2093 1157
2093 1257
2093 1357
1374 905
1474 905
1574 905
1674 905
1774 905
1874 905
1974 905
2074 905
2174 905
2274 905
1339 166
1339 266
1339 366
1339 466
1339 566
1339 666
1339 766
1339 866
1339 966
1339 1066
1339 1166
1556 599
1656 599
1756 599
1856 599
1956 599
2056 599
2156 599
2256 599
2356 599
2456 599
2581 854
2581 954
2581 1054
2581 1154
2581 1254
2581 1354
767 217
867 217
967 217
1067 217
1167 217
1267 217
1367 217
1467 217
1567 217
951 541
951 641
951 741
951 841
951 941
951 1041
951 1141
951 1241
951 1341
1991 1468
2091 1468
2191 1468
2291 1468
2391 1468
2491 1468
Test Case 26
3000 1500 200
1
1993 157
2093 157
2193 157
2293 157
2393 157
2493 157
2593 157
2693 157
2793 157
2893 157
1338 895
1338 995
1338 1095
1338 1195
1338 1295
1338 1395
952 29
1052 29
1152 29
1252 29
1352 29
1452 29
1552 29
1652 29
1752 29
732 347
732 447
732 547
732 647
732 747
732 847
732 947
732 1047
732 1147
732 1247
732 1347
1895 357
1995 357
2095 357
2195 357
2295 357
2395 357
2495 357
2595 357
961 782
961 882
961 982
961 1082
961 1182
961 1282
1641 307
1741 307
1841 307
1941 307
2041 307
2141 307
2241 307
2341 307
50 865
50 965
50 1065
50 1165
50 1265
50 1365
1922 1381
2022 1381
2122 1381
2222 1381
2322 1381
2422 1381
2522 1381
2622 1381
2722 1381
2287 161
2287 261
2287 361
2287 461
2287 561
2287 661
2287 761
2287 861
2287 961
247 1264
347 1264
447 1264
547 1264
647 1264
747 1264
847 1264
947 1264
1047 1264
1147 1264
1247 1264
1933 276
1933 376
1933 476
1933 576
1933 676
1933 776
1933 876
1933 976
1933 1076
1933 1176
1117 385
1217 385
1317 385
1417 385
1517 385
1617 385
1717 385
1001 21
1001 121
1001 221
1001 321
1001 421
1001 521
1001 621
1001 721
1001 821
1001 921
1001 1021
340 1137
440 1137
540 1137
640 1137
740 1137
840 1137
940 1137
https://onlinecourses.nptel.ac.in/noc19_cs11/progassignment?name=102 25/29
3/4/2019 Design and Analysis of Algorithms - Course
1340 135
1340 235
1340 335
1340 435
1340 535
1340 635
1340 735
953 531
1053 531
1153 531
1253 531
1353 531
1453 531
1553 531
1653 531
1753 531
1853 531
1953 531
2592 464
2592 564
2592 664
2592 764
2592 864
2592 964
2592 1064
2592 1164
2592 1264
2592 1364
1463 17
1563 17
1663 17
1763 17
1863 17
1963 17
2063 17
2163 17
2263 17
2363 17
654 576
654 676
654 776
654 876
654 976
654 1076
654 1176
654 1276
654 1376
654 1476
684 1461
784 1461
884 1461
984 1461
1084 1461
1184 1461
1284 1461
1384 1461
1484 1461
1584 1461
231
331
431
531
631
731
831
931
1031
1131
1211 95
1311 95
1411 95
1511 95
