13084 - Cameras as Invigilators

All about problems in Volume 130. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Post Reply
dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

13084 - Cameras as Invigilators

Post by dibery » Wed Apr 20, 2016 5:06 am

Getting several WA for this problem.
I've tried many solutions but none worked.

Here's my solution: (spoiler below)

1. Generate all lines that can be drawn in 5001x5001 grid. (As the longest line is 5000x5000, I didn't generate lines longer than 5000.)
2. For each possible line (sorted in order), check lines forward. If these 2 lines are trouble with each other, mark all points on both lines as troubled.
3. Check 2D array to see which points are troubled. As the cameras are symmetric, I check from one side and take the symmetry of it.

Code: Select all

Code removed after AC.
Also some IO:
Input

Code: Select all

1000
57 1238
87 3028
62 3379
52 1359
47 1878
33 440
61 1118
75 343
72 2585
28 343
83 6088
68 1726
27 601
86 5618
63 1060
29 241
21 339
22 155
38 1346
56 2002
88 4933
53 2500
13 124
80 5457
63 1590
82 5790
47 889
87 3064
51 2338
46 854
21 217
29 109
67 3573
80 4197
79 5996
65 1637
36 34
78 4413
89 5236
88 116
28 679
61 222
84 192
72 1251
83 271
44 900
68 3109
69 1053
78 3310
35 312
49 673
54 2193
61 2797
89 797
85 3859
64 3805
62 1581
63 1544
67 3634
44 914
47 977
17 22
35 1023
13 98
30 580
80 3611
71 1652
39 754
60 60
76 4333
19 281
21 141
28 720
38 875
61 3240
88 856
44 117
34 339
17 134
82 336
50 882
81 2178
58 248
47 809
42 227
26 194
26 187
66 330
53 2349
71 239
61 32
65 1437
10 91
59 2929
21 347
78 1864
66 4251
67 2790
42 1375
85 3214
32 972
68 534
33 450
34 251
33 905
43 236
59 617
73 1149
34 452
68 4051
36 126
81 713
67 1727
68 3177
58 2262
84 3382
60 2084
23 239
49 784
22 210
85 6133
50 825
80 1895
25 84
18 321
12 34
33 836
78 140
36 1054
52 1242
46 1376
11 111
82 1342
42 363
61 1301
87 5395
36 293
54 2529
55 694
73 2590
46 285
49 2202
53 503
21 437
67 3101
58 2326
51 1989
62 3178
73 3832
59 1618
75 1889
75 2403
78 449
70 2513
18 296
48 1196
23 134
65 3521
18 159
88 5618
82 1642
74 4558
89 4146
62 2990
35 798
10 62
62 806
15 116
57 2778
36 104
24 129
14 47
24 252
46 87
41 938
51 483
26 129
51 2338
23 237
71 4847
29 16
42 603
89 4359
74 1795
18 143
65 79
38 363
43 155
33 296
27 67
17 4
72 263
45 528
80 5201
79 1553
33 354
75 1373
41 1046
88 4752
25 521
21 360
70 2319
44 845
11 44
45 1664
74 3218
39 1258
60 817
31 734
60 1162
86 921
12 45
11 40
71 3784
44 621
47 150
61 1482
46 921
25 4
57 2200
50 1523
86 3154
71 2140
49 1145
33 513
87 4699
76 3551
74 4272
27 140
61 1675
84 2777
10 26
20 356
13 18
68 1986
37 126
75 5109
50 666
64 2527
11 63
34 1150
58 2795
39 1317
41 448
40 434
60 824
85 2561
32 870
49 1955
73 4120
70 1351
78 2330
77 3831
54 2653
54 2069
81 651
85 1044
89 268
82 6350
34 82
59 1417
40 1004
87 554
12 117
73 342
48 747
39 652
35 943
49 1903
51 898
29 838
33 792
82 1307
82 5552
47 1311
32 294
52 1428
13 139
67 4062
39 433
65 582
78 1872
88 3213
14 9
45 1421
82 1711
40 367
32 982
32 942
32 828
24 556
60 1736
27 660
58 1626
53 1181
77 2574
27 20
65 1520
62 1119
14 156
67 3912
57 2418
85 3794
72 2562
77 2204
72 225
11 34
67 720
48 570
87 3473
17 120
61 3464
33 272
81 2252
48 1963
77 1215
17 147
65 3173
65 140
15 92
37 977
53 1381
61 3136
41 1352
41 1308
52 2358
54 2238
25 4
82 1398
56 3038
28 690
88 5481
62 2545
70 928
85 2245
80 2694
62 3170
45 169
81 5010
75 564
56 2140
22 450
36 427
71 1826
60 1659
11 39
87 3751
55 885
46 906
88 5072
21 192
48 1056
16 121
82 5525
21 433
61 1099
79 3808
61 1763
37 948
76 5629
54 2483
27 658
60 2783
21 313
19 3
32 484
40 173
30 448
48 380
76 3202
64 4021
21 2
47 844
21 3
57 2641
72 4315
58 1604
63 1287
25 324
18 284
36 15
86 2716
86 4637
54 514
71 3827
30 227
62 2120
73 498
89 2507
36 622
65 436
20 343
83 962
83 6091
89 344
42 1185
26 240
43 771
71 1622
41 263
22 295
72 3696
45 1845
68 674
81 1796
43 331
87 1985
31 617
68 686
40 1577
10 54
45 216
37 848
71 4058
60 2332
13 4
73 3262
41 1230
73 980
47 1223
88 1254
63 3659
75 5622
60 2683
35 1042
63 3365
57 526
84 5626
70 1367
44 1903
61 3261
56 3074
18 81
47 2057
81 5105
88 1925
27 87
58 1563
41 1200
56 328
13 159
44 1298
21 323
38 824
29 61
65 785
14 13
66 964
12 78
78 585
51 1389
56 1674
80 3727
23 134
27 423
40 52
73 5102
64 1531
86 5134
29 583
59 1013
15 125
89 2547
60 3361
37 939
69 297
34 49
89 3946
34 460
78 134
34 882
24 328
76 2229
45 1249
33 382
71 3827
42 350
88 5583
10 40
74 187
48 1691
58 810
31 401
71 3216
21 53
49 102
62 58
38 75
37 380
15 52
31 281
37 573
15 222
46 973
67 1232
27 679
58 1005
71 3015
26 75
28 747
87 500
89 4271
26 567
34 587
52 942
87 2788
59 152
78 518
43 1787
22 162
71 2821
51 306
88 4679
12 46
60 580
35 1059
40 985
10 98
14 109
83 756
17 118
72 2296
89 5533
40 305
21 238
69 523
65 4101
15 145
54 899
61 3070
38 737
55 795
16 109
19 302
64 1378
19 62
67 3819
79 5067
37 1267
84 5990
88 2453
25 104
84 3140
69 2646
38 631
46 852
22 401
60 2338
41 810
38 965
24 422
61 2066
72 4664
10 61
54 1846
41 1101
58 2126
59 956
77 4966
43 641
53 1485
65 3647
65 960
35 453
47 1346
85 1646
86 390
52 682
81 5777
61 563
79 407
40 837
11 93
10 48
54 1157
45 1259
48 26
57 1274
29 57
13 126
72 4063
69 2830
87 5020
78 3344
59 1856
66 614
36 358
86 6155
32 412
57 3123
55 1542
35 853
86 3172
59 238
59 2738
34 719
13 31
20 273
67 3823
31 629
64 2749
75 1275
30 81
37 989
51 2535
38 1202
38 401
51 568
88 1514
81 2251
25 447
88 1458
61 1215
61 2653
81 5716
17 225
16 232
87 2728
15 129
78 1970
60 2976
14 58
32 621
16 116
18 265
29 316
87 4763
83 3010
20 317
38 145
32 915
40 1228
69 3222
65 3786
13 3
24 197
22 162
13 98
58 1757
16 184
80 2665
73 3813
84 3528
45 489
63 863
47 1089
61 140
66 3067
24 239
89 2434
68 2510
64 134
26 209
66 3308
60 3182
82 5461
49 449
38 1246
74 880
80 837
74 4632
27 601
57 3107
60 1374
18 182
25 481
26 446
67 1701
89 2946
59 2793
10 61
21 149
59 834
35 508
49 1586
32 519
38 19
21 323
74 205
83 2085
25 224
69 2934
89 7005
26 182
63 2554
10 25
68 1483
55 1754
77 4665
54 998
80 3987
12 34
68 2077
88 6763
68 567
45 1291
42 78
19 197
44 761
72 2648
84 1646
55 1228
68 4138
74 5281
27 426
81 4651
26 65
20 394
80 4840
79 2392
73 4578
37 618
33 208
41 915
24 413
12 136
70 3867
23 1
52 1374
13 48
69 4448
28 635
62 1352
31 598
30 803
37 503
30 766
62 2799
53 2200
15 44
11 99
59 3059
17 60
29 493
23 215
70 2684
10 58
29 9
69 2456
41 808
77 2085
45 1952
27 371
13 147
53 2511
31 297
58 1854
67 4432
47 1775
66 362
60 1556
36 898
44 1357
17 121
32 854
55 2794
58 3264
27 267
50 1392
87 2804
22 146
41 1047
83 6882
77 5762
46 499
75 793
89 4020
50 1386
19 213
41 1096
79 5201
50 1918
39 467
65 2766
71 4964
18 42
65 71
16 224
41 1030
73 4977
79 842
67 1969
69 1241
17 6
27 487
61 1155
77 1049
86 2216
15 154
31 123
19 171
55 1781
62 3803
27 291
39 418
32 595
10 39
50 1979
58 147
42 1057
47 1401
34 760
89 7465
66 2137
66 2913
34 301
68 3429
44 910
34 251
27 708
13 115
83 1136
80 385
24 407
74 378
66 3005
12 80
40 513
15 78
48 573
46 1910
41 1516
45 425
71 1699
78 4514
76 503
80 5899
68 4332
86 1776
29 444
81 2821
43 1058
70 2395
36 513
64 3969
41 753
73 5063
50 1211
89 1073
73 1322
62 2341
52 1242
70 2860
32 808
54 2462
78 3675
32 565
38 1158
79 2643
62 2815
34 19
47 1257
27 249
20 208
61 733
77 4639
84 3373
75 2506
11 31
72 2189
43 1453
11 5
66 2625
52 1053
78 1374
82 4768
11 29
14 42
68 3262
76 4845
82 6089
14 94
76 2821
83 5860
71 4798
42 1582
20 385
16 114
57 1436
25 10
56 791
10 47
46 1788
27 204
60 1043
38 1146
50 1284
71 1278
16 70
23 129
23 265
75 3890
73 526
35 900
33 1011
75 2739
57 654
46 675
31 457
12 136
50 1802
76 5056
56 2639
36 1204
15 144
81 284
47 503
36 1092
42 1028
12 72
54 15
87 4979
15 36
89 5374
81 2222
28 544
25 227
42 454
14 19
76 2186
60 3290
23 511
29 190
21 435
85 4703
21 36
43 970
14 146
37 147
74 4954
47 177
12 36
82 1343
76 2668
88 629
80 3200
73 4086
82 5514
85 343
79 2881
59 773
40 1362
84 4898
50 1361
80 664
33 796
69 173
41 530
55 2605
42 391
65 882
37 1273
68 1523
34 449
65 2565
85 2714
88 6874
68 1640
54 618
55 2996
84 405
55 441
57 2404
19 252
89 2823
81 291
58 2482
86 6094
80 1300
41 381
27 547
31 13
46 1359
18 221
59 2766
29 50
85 5505
43 393
24 443
80 525
78 1777
61 997
73 1887
56 1253
29 635
60 2196
18 315
14 76
64 1741
87 3322
61 316
13 77
76 5028
34 624
41 553
87 7527
37 246
50 1742
57 2189
58 2646
Output:

Code: Select all

1248
2714
74
634
64
430
1786
5004
1427
239
82
1895
28
478
2326
432
16
238
25
391
954
48
10
159
1498
162
768
2678
32
751
106
664
136
790
44
1582
1367
501
666
7656
20
3340
6807
3309
6478
563
476
3012
1358
744
1302
185
176
6512
1298
49
1397
1544
130
559
652
272
30
32
131
1217
2262
372
3540
351
22
208
11
222
64
6316
1723
604
78
6212
1144
3010
2948
878
1414
360
384
3812
72
4598
3842
1876
1
86
14
3169
23
512
94
2014
11
3720
406
744
30
1454
2404
3260
457
112
1086
5324
1568
432
329
2179
717
150
1100
159
144
1230
3419
476
4
95
50
6006
62
780
253
2
4388
1189
1512
486
861
84
1888
1194
1592
26
1912
2
306
308
108
117
314
902
2660
1902
5384
1180
8
599
310
96
98
581
3900
187
1500
201
94
16
2458
50
74
1127
391
120
212
2070
272
1800
470
32
150
16
898
863
1292
2588
117
4160
862
1582
634
650
322
4746
1186
234
3496
508
3496
182
1069
16
10
1396
633
58
56
940
46
2383
42
1911
5726
86
58
220
972
1978
1230
670
674
248
403
2406
1520
580
296
924
816
299
500
960
2985
58
7
156
1502
1140
58
1462
610
30
4
110
32
878
947
2383
2970
24
66
212
2768
2522
546
56
266
5494
5420
7480
53
1057
1152
228
6558
9
4704
1184
506
52
86
1152
6
72
4482
213
306
564
569
6
60
860
3242
3161
2663
223
146
3850
1059
11
13
39
2
1099
14
880
842
1732
782
1746
2042
13
78
172
1340
1460
2276
4835
70
3206
1460
2108
92
30
648
2888
71
3910
68
186
4032
84
96
614
84
64
72
47
171
674
4306
15
20
631
482
3459
3466
2326
117
1754
270
4664
287
8
672
1910
1184
58
1804
1574
676
844
140
787
75
217
2
1860
734
896
104
25
97
16
216
18
398
310
1332
273
1712
1082
21
482
830
482
100
192
898
1940
128
8
1367
3090
1037
2098
198
563
755
4416
3592
377
3460
8
5146
82
7364
217
304
584
2294
1176
69
476
26
3518
3602
1254
4306
98
3478
12
24
1668
136
162
526
194
620
94
3548
398
5684
36
18
270
28
80
2306
349
2762
10
62
15
196
26
236
4613
568
937
108
2611
2
229
18
263
756
2876
223
2808
38
5086
510
672
1131
310
128
1560
26
1690
700
58
1772
38
3560
36
104
4178
1122
1698
455
6006
56
119
2279
268
476
198
1189
593
46
5112
191
2018
338
474
344
2256
3967
1333
690
144
476
422
2
627
2346
12
1726
588
552
9
6764
1358
30
298
1192
3068
3190
5217
10
220
788
2076
1140
86
2733
22
246
1
53
5554
100
1812
532
1139
86
3860
22
22
1549
98
346
1706
90
20
1915
270
86
160
22
210
3801
476
2479
866
472
761
21
518
388
176
57
588
79
16
460
154
404
1842
122
756
506
68
2614
520
284
4416
6664
1617
112
2708
5566
323
8
24
1167
264
2399
1214
756
10
305
700
676
1338
632
3328
736
245
409
16
654
68
2392
3114
130
165
132
46
86
96
468
3660
762
92
16
49
820
1646
5282
2888
44
5330
1668
238
120
18
6
3212
34
3007
132
110
190
88
19
322
878
1966
19
1212
16
91
388
52
194
284
220
32
737
23
2371
334
1988
1258
2612
516
3540
407
220
3732
977
3907
354
286
68
242
1636
48
3922
5058
174
28
16
1607
79
36
96
1630
2946
120
16
200
2068
382
216
260
1519
18
5112
3354
254
612
110
384
440
58
2238
448
194
1410
930
95
1390
178
3644
234
1722
68
780
1371
4599
1026
91
38
128
436
552
3
358
2224
100
366
724
288
59
0
220
574
623
92
52
31
1676
114
18
516
25
293
96
160
6
56
188
114
178
1026
16
898
1044
392
2448
12
182
4
48
464
636
14
86
3768
1341
122
196
92
28
36
31
314
518
3040
250
182
22
24
1270
4314
1620
524
58
156
138
150
750
426
12
273
4160
10
192
42
4714
1226
2740
322
66
1710
4174
3770
22
770
122
424
20
294
860
207
46
118
3080
347
254
142
56
1221
520
684
305
559
744
6
22
4892
5745
59
4848
438
38
788
104
1460
40
18
1354
2162
452
4854
67
51
4442
180
2074
298
1316
503
25
456
26
725
5914
3046
600
780
856
45
99
1035
228
59
1916
292
1223
374
344
112
2408
204
2187
1760
70
1922
80
142
738
1069
3862
521
70
132
385
141
90
58
1488
134
18
24
3
88
970
674
1851
24
61
410
2136
71
618
2850
139
326
124
484
4376
58
14
1506
2116
996
250
0
219
95
101
12
22
6058
1338
46
386
46
3023
716
182
598
2922
63
254
1047
182
2376
56
4
506
2
652
420
378
13
1140
88
1918
95
4388
1697
6662
1599
220
219
6696
1588
2174
46
742
544
5268
68
4424
780
70
1154
2764
20
2208
465
522
2774
149
2042
1888
10
6372
2336
176
38
3178
6058
237
264
4353
1022
48
1022
266
45
130
812
294
1150
43
5524
3367
1980
2070
1205
48
610
4
86
1403
2348
3200
58
99
257
756
18
926
253
252
165
Is my output correct?
Any help would be appreciated.

EDIT: This cases above is checked after getting AC, so I left them here for people who might need.

One more case, "5000 25000000" has 65631 troubled points.
Life shouldn't be null.

Post Reply

Return to “Volume 130 (13000-13099)”