QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#405509#5426. Drain the Water TankFOY#AC ✓1ms3700kbC++231.1kb2024-05-06 02:20:412024-05-06 02:20:42

Judging History

你现在查看的是最新测评结果

  • [2024-05-06 02:20:42]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3700kb
  • [2024-05-06 02:20:41]
  • 提交

answer

#include <iostream>
#include <vector>
#include <set>
#include <cassert>
using namespace std;
using pii = pair<int, int>;

const int mn = 2e3 + 5;
pii poly[3*mn];

set<int> drain1, drain2;

pii sub(pii a, pii b) {
	return {a.first - b.first, a.second - b.second};
}

int cross(pii l, pii r) {
	return l.first * r.second - r.first * l.second;
}

int main() {
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> poly[i].first >> poly[i].second;
		poly[i+n] = poly[i];
		poly[i+2*n] = poly[i];
	}
	
	int cnt = 0;
	int lo1 = 1e9, lo2 = 1e9;
	for (int i = n; i < 2*n; i++) {
		if (poly[i-1].second > poly[i].second && poly[i+1].second >= poly[i].second) {
			while (poly[i+1].second == poly[i].second) i++;
			int dir = cross(sub(poly[i-1], poly[i]), sub(poly[i+1], poly[i]));
			assert(dir != 0);
			if (poly[i+1].second > poly[i].second) {
				if (dir > 0) {
					drain1.insert(i%n);
					lo1 = min(lo1, poly[i].second);
				}
				else if (dir < 0) {
					drain2.insert(i%n);
					lo2 = min(lo2, poly[i].second);
				}
			}
		}
	}
	if (lo2 < lo1) swap(drain1, drain2);
	cout << drain1.size() << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3548kb

input:

6
0 0
1 1
2 1
3 0
3 2
0 2

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

8
4 4
0 4
0 2
1 2
2 2
2 0
3 0
4 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

7
1 0
3 4
0 3
1 2
2 3
1 1
0 2

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

6
0 0
2 0
1 1
4 1
5 0
3 4

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

8
0 0
1 0
3 -1
3 0
1 1
4 1
5 0
3 4

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

5
0 0
170 0
140 30
60 30
0 70

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

5
0 0
170 0
140 30
60 30
0 100

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

5
0 0
1 2
1 5
0 2
0 1

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

3
0 0
100 0
0 100

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3424kb

input:

3
200 0
100 100
0 0

output:

1

result:

ok 1 number(s): "1"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

3
50 50
100 50
100 100

output:

1

result:

ok 1 number(s): "1"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

3
3 0
0 4
0 0

output:

1

result:

ok 1 number(s): "1"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3552kb

input:

3
10000 10000
-10000 10000
10000 9999

output:

1

result:

ok 1 number(s): "1"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3444kb

input:

3
10000 10000
-10000 10000
10000 9900

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

3
10000 10000
9999 10000
10000 -10000

output:

1

result:

ok 1 number(s): "1"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

3
0 0
200 0
100 173

output:

1

result:

ok 1 number(s): "1"

Test #17:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

3
0 0
200 0
100 1

output:

1

result:

ok 1 number(s): "1"

Test #18:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3
-10000 -10000
10000 9999
9999 10000

output:

1

result:

ok 1 number(s): "1"

Test #19:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

4
10 10
20 10
20 20
10 20

output:

1

result:

ok 1 number(s): "1"

Test #20:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

4
-10000 -10000
10000 -10000
10000 10000
-10000 10000

output:

1

result:

ok 1 number(s): "1"

Test #21:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

4
100 0
200 100
100 200
0 100

output:

1

result:

ok 1 number(s): "1"

Test #22:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

4
0 1
100 0
101 100
1 101

output:

1

result:

ok 1 number(s): "1"

Test #23:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

4
0 0
100 0
100 50
0 50

output:

1

result:

ok 1 number(s): "1"

Test #24:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

4
0 0
50 0
50 100
0 100

output:

1

result:

ok 1 number(s): "1"

Test #25:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

4
0 10
10 0
100 90
90 100

output:

1

result:

ok 1 number(s): "1"

Test #26:

score: 0
Accepted
time: 0ms
memory: 3448kb

input:

8
0 100
100 0
250 0
350 100
350 250
250 350
100 350
0 250

output:

1

result:

ok 1 number(s): "1"

Test #27:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

6
0 50
10 0
70 0
80 10
70 50
50 80

output:

1

result:

ok 1 number(s): "1"

Test #28:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

4
0 100
0 0
100 0
20 20

output:

1

result:

ok 1 number(s): "1"

Test #29:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

4
0 100
55 55
100 0
100 100

output:

1

result:

ok 1 number(s): "1"

Test #30:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

8
0 0
100 0
100 20
40 20
40 40
100 40
100 60
0 60

output:

1

result:

ok 1 number(s): "1"

Test #31:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

12
0 0
90 0
90 30
40 30
40 40
90 40
90 50
0 50
0 20
50 20
50 10
0 10

output:

1

result:

ok 1 number(s): "1"

Test #32:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

12
0 0
100 0
100 100
10 100
10 110
200 110
200 60
101 60
101 40
210 40
210 120
0 120

output:

2

result:

ok 1 number(s): "2"

Test #33:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

10
1000 0
1100 0
1200 100
1220 200
1200 110
1100 10
1000 10
900 110
880 200
900 100

output:

1

result:

ok 1 number(s): "1"

Test #34:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

16
0 0
60 0
60 70
0 70
0 20
40 20
40 50
20 50
20 40
30 40
30 30
10 30
10 60
50 60
50 10
0 10

output:

2

result:

ok 1 number(s): "2"

Test #35:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

8
0 1
100 0
5 5
200 5
105 0
205 1
205 10
0 10

output:

2

result:

ok 1 number(s): "2"

Test #36:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

8
0 1
50 0
5 5
200 5
150 0
205 1
205 10
0 10

output:

2

result:

ok 1 number(s): "2"

Test #37:

score: 0
Accepted
time: 0ms
memory: 3444kb

input:

9
99 100
100 100
99 99
301 99
300 100
301 100
201 274
200 273
199 274

output:

1

result:

ok 1 number(s): "1"

Test #38:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

15
0 0
10 0
20 0
30 0
40 0
50 0
40 10
30 20
20 30
10 40
0 50
0 40
0 30
0 20
0 10

output:

1

result:

ok 1 number(s): "1"

Test #39:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

11
0 0
100 0
90 5
80 10
70 15
60 20
50 25
40 20
30 15
20 10
10 5

output:

1

result:

ok 1 number(s): "1"

Test #40:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

8
0 0
20 30
0 60
0 50
0 40
0 30
0 20
0 10

output:

1

result:

ok 1 number(s): "1"

Test #41:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

18
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 30
120 60
120 90
120 120
80 120
40 120
0 120
0 96
0 72
0 48
0 24

output:

1

result:

ok 1 number(s): "1"

Test #42:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

15
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
80 120
40 120
0 120
0 96
0 72
0 48
0 24

output:

1

result:

ok 1 number(s): "1"

Test #43:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

11
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
80 120
40 120
0 120

output:

1

result:

ok 1 number(s): "1"

Test #44:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

9
0 0
20 0
40 0
60 0
80 0
100 0
120 0
120 120
0 120

output:

1

result:

ok 1 number(s): "1"

Test #45:

score: 0
Accepted
time: 0ms
memory: 3448kb

input:

29
0 0
100 0
100 50
0 50
0 20
80 20
80 30
10 30
10 40
20 40
30 40
40 40
50 40
60 40
70 40
80 40
90 40
90 30
90 20
90 10
80 10
70 10
60 10
50 10
40 10
30 10
20 10
10 10
0 10

output:

2

result:

ok 1 number(s): "2"

Test #46:

score: 0
Accepted
time: 0ms
memory: 3448kb

input:

24
0 0
100 0
100 100
200 100
200 0
300 0
300 100
300 200
200 200
200 300
300 300
300 400
300 500
200 500
200 400
100 400
100 500
0 500
0 400
0 300
100 300
100 200
0 200
0 100

output:

2

result:

ok 1 number(s): "2"

Test #47:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

4
50 50
100 50
100 101
50 100

output:

1

result:

ok 1 number(s): "1"

Test #48:

score: 0
Accepted
time: 0ms
memory: 3460kb

input:

10
100 300
150 50
100 0
200 50
250 150
250 50
400 0
300 50
350 50
400 300

output:

2

result:

ok 1 number(s): "2"

Test #49:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

10
300 400
50 350
50 300
0 400
50 250
150 250
50 200
0 100
50 150
300 100

output:

2

result:

ok 1 number(s): "2"

Test #50:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

5
0 0
100 100
60 40
200 200
40 60

output:

2

result:

ok 1 number(s): "2"

Test #51:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

5
0 0
100 100
60 40
120 120
40 60

output:

2

result:

ok 1 number(s): "2"

Test #52:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

5
0 0
100 100
51 49
200 200
49 51

output:

2

result:

ok 1 number(s): "2"

Test #53:

score: 0
Accepted
time: 0ms
memory: 3448kb

input:

5
100 10
300 0
200 10
400 10
300 20

output:

1

result:

ok 1 number(s): "1"

Test #54:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

5
20 300
10 400
10 200
0 300
10 100

output:

1

result:

ok 1 number(s): "1"

Test #55:

score: 0
Accepted
time: 0ms
memory: 3444kb

input:

10
110 171
57 121
56 102
7 17
101 24
65 34
70 43
157 6
134 20
93 54

output:

2

result:

ok 1 number(s): "2"

Test #56:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

28
90 55
160 20
323 47
418 138
371 386
367 225
321 305
306 115
284 436
281 216
233 86
231 227
219 312
216 405
213 45
184 92
182 345
168 462
155 275
136 107
106 211
100 159
94 308
85 232
62 413
43 160
0 338
16 95

output:

1

result:

ok 1 number(s): "1"

Test #57:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

28
-90 -55
-160 -20
-323 -47
-418 -138
-371 -386
-367 -225
-321 -305
-306 -115
-284 -436
-281 -216
-233 -86
-231 -227
-219 -312
-216 -405
-213 -45
-184 -92
-182 -345
-168 -462
-155 -275
-136 -107
-106 -211
-100 -159
-94 -308
-85 -232
-62 -413
-43 -160
0 -338
-16 -95

output:

9

result:

ok 1 number(s): "9"

Test #58:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

100
10000 0
9980 627
9921 1253
9822 1873
9685 2486
9510 3090
9297 3681
9048 4257
8763 4817
8443 5358
8090 5877
7705 6374
7289 6845
6845 7289
6374 7705
5877 8090
5358 8443
4817 8763
4257 9048
3681 9297
3090 9510
2486 9685
1873 9822
1253 9921
627 9980
0 10000
-627 9980
-1253 9921
-1873 9822
-2486 9685...

output:

1

result:

ok 1 number(s): "1"

Test #59:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

500
10000 0
9999 125
9996 251
9992 376
9987 502
9980 627
9971 753
9961 878
9949 1003
9936 1128
9921 1253
9904 1377
9886 1502
9866 1626
9845 1750
9822 1873
9798 1997
9772 2120
9745 2242
9716 2364
9685 2486
9653 2608
9620 2729
9585 2850
9548 2970
9510 3090
9470 3209
9429 3328
9387 3446
9343 3564
9297 ...

output:

1

result:

ok 1 number(s): "1"

Test #60:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

1000
10000 0
9999 62
9999 125
9998 188
9996 251
9995 314
9992 376
9990 439
9987 502
9984 565
9980 627
9976 690
9971 753
9966 815
9961 878
9955 941
9949 1003
9943 1066
9936 1128
9928 1190
9921 1253
9913 1315
9904 1377
9895 1440
9886 1502
9876 1564
9866 1626
9856 1688
9845 1750
9834 1812
9822 1873
981...

output:

1

result:

ok 1 number(s): "1"

Test #61:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

100
5675 0
5096 320
9219 1164
6323 1206
5537 1421
7180 2332
8787 3479
8780 4131
6560 3606
6417 4072
7534 5474
7349 6079
5101 4790
5742 6115
4154 5021
4618 6356
3825 6027
2789 5073
3987 8472
2099 5301
2014 6198
1762 6862
1775 9307
858 6793
397 6323
0 6011
-498 7921
-654 5183
-1292 6776
-1406 5476
-20...

output:

17

result:

ok 1 number(s): "17"

Test #62:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

500
9861 0
6812 85
7520 189
7380 278
5178 260
7253 456
6724 507
7648 674
6898 695
5518 626
5005 632
9331 1298
4943 751
9438 1555
6461 1148
9637 1838
5312 1082
9406 2040
8241 1896
8053 1960
8715 2237
6398 1728
5037 1429
4855 1443
7371 2293
7768 2524
8513 2884
9057 3196
6740 2474
8789 3352
5730 2269
8...

output:

82

result:

ok 1 number(s): "82"

Test #63:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

1000
8091 0
9198 57
9060 113
5747 108
5479 137
6865 215
9352 352
7129 313
5012 252
5016 283
7401 465
8909 616
9970 753
9436 772
7619 671
5368 507
6896 695
8556 917
6143 697
6802 816
9764 1233
9025 1197
8619 1199
5442 792
8519 1294
8530 1351
8292 1366
8711 1492
9103 1618
8293 1528
6769 1291
9047 1784...

output:

157

result:

ok 1 number(s): "157"

Test #64:

score: 0
Accepted
time: 0ms
memory: 3464kb

input:

100
0 0
10000 0
10000 10000
9896 9853
9793 951
9690 1642
9587 4776
9484 6666
9381 5058
9278 8146
9175 6491
9072 714
8969 1675
8865 79
8762 3597
8659 4040
8556 1707
8453 8735
8350 6676
8247 8796
8144 2579
8041 2431
7938 3240
7835 827
7731 353
7628 5638
7525 1960
7422 7770
7319 8599
7216 5076
7113 880...

output:

1

result:

ok 1 number(s): "1"

Test #65:

score: 0
Accepted
time: 1ms
memory: 3480kb

input:

500
0 0
10000 0
10000 10000
9979 4349
9959 5502
9939 255
9919 639
9899 5248
9879 974
9859 7593
9839 1091
9818 5905
9798 6216
9778 8699
9758 9951
9738 2044
9718 8181
9698 5522
9678 1888
9657 7549
9637 9475
9617 3347
9597 136
9577 775
9557 2467
9537 1000
9517 3873
9496 1460
9476 4350
9456 7880
9436 48...

output:

1

result:

ok 1 number(s): "1"

Test #66:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

1000
0 0
10000 0
10000 10000
9989 4685
9979 9134
9969 1180
9959 3397
9949 6194
9939 3697
9929 7962
9919 1358
9909 5778
9899 6522
9889 6286
9879 2382
9869 41
9859 3865
9849 997
9839 1746
9829 8380
9819 8211
9809 6070
9799 5539
9789 7476
9779 4391
9769 4092
9759 9264
9749 2333
9739 3849
9729 6011
9719...

output:

1

result:

ok 1 number(s): "1"

Test #67:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

1000
0 0
-10000 0
-10000 -10000
-9989 -4685
-9979 -9134
-9969 -1180
-9959 -3397
-9949 -6194
-9939 -3697
-9929 -7962
-9919 -1358
-9909 -5778
-9899 -6522
-9889 -6286
-9879 -2382
-9869 -41
-9859 -3865
-9849 -997
-9839 -1746
-9829 -8380
-9819 -8211
-9809 -6070
-9799 -5539
-9789 -7476
-9779 -4391
-9769 -...

output:

339

result:

ok 1 number(s): "339"

Test #68:

score: 0
Accepted
time: 0ms
memory: 3444kb

input:

100
-25 0
-24 0
-23 0
-22 0
-21 0
-20 0
-19 0
-18 0
-17 0
-16 0
-15 0
-14 0
-13 0
-12 0
-11 0
-10 0
-9 0
-8 0
-7 0
-6 0
-5 0
-4 0
-3 0
-2 0
-1 0
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
-9999 1
9999 2
-9999 3
9999 4
-9999 5
99...

output:

1

result:

ok 1 number(s): "1"

Test #69:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

500
-125 0
-124 0
-123 0
-122 0
-121 0
-120 0
-119 0
-118 0
-117 0
-116 0
-115 0
-114 0
-113 0
-112 0
-111 0
-110 0
-109 0
-108 0
-107 0
-106 0
-105 0
-104 0
-103 0
-102 0
-101 0
-100 0
-99 0
-98 0
-97 0
-96 0
-95 0
-94 0
-93 0
-92 0
-91 0
-90 0
-89 0
-88 0
-87 0
-86 0
-85 0
-84 0
-83 0
-82 0
-81 0
...

output:

1

result:

ok 1 number(s): "1"

Test #70:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

1000
-250 0
-249 0
-248 0
-247 0
-246 0
-245 0
-244 0
-243 0
-242 0
-241 0
-240 0
-239 0
-238 0
-237 0
-236 0
-235 0
-234 0
-233 0
-232 0
-231 0
-230 0
-229 0
-228 0
-227 0
-226 0
-225 0
-224 0
-223 0
-222 0
-221 0
-220 0
-219 0
-218 0
-217 0
-216 0
-215 0
-214 0
-213 0
-212 0
-211 0
-210 0
-209 0
-...

output:

1

result:

ok 1 number(s): "1"

Test #71:

score: 0
Accepted
time: 0ms
memory: 3464kb

input:

4
0 0
2000 0
1500 866
500 866

output:

1

result:

ok 1 number(s): "1"

Test #72:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

4
0 0
2000 0
1500 867
500 867

output:

1

result:

ok 1 number(s): "1"

Test #73:

score: 0
Accepted
time: 1ms
memory: 3568kb

input:

4
0 0
1000 0
1500 866
1000 1732

output:

1

result:

ok 1 number(s): "1"

Test #74:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

4
0 0
1000 0
1500 867
1000 1733

output:

1

result:

ok 1 number(s): "1"

Test #75:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

2000
-10000 9938
-10000 9914
-10000 9873
-10000 9831
-10000 9739
-10000 9710
-10000 9608
-10000 9595
-10000 9537
-10000 9524
-10000 9485
-10000 9470
-10000 9450
-10000 9428
-10000 9410
-10000 9376
-10000 9373
-10000 9321
-10000 9271
-10000 9245
-10000 9200
-10000 9027
-10000 9002
-10000 8959
-10000 ...

output:

1

result:

ok 1 number(s): "1"

Test #76:

score: 0
Accepted
time: 1ms
memory: 3424kb

input:

4
-10000 0
0 -10000
10000 0
0 10000

output:

1

result:

ok 1 number(s): "1"

Test #77:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

2000
-93 9907
-98 9902
-100 9900
-101 9899
-123 9877
-180 9820
-192 9808
-196 9804
-197 9803
-238 9762
-253 9747
-268 9732
-282 9718
-290 9710
-294 9706
-334 9666
-428 9572
-466 9534
-474 9526
-477 9523
-486 9514
-504 9496
-534 9466
-536 9464
-573 9427
-605 9395
-612 9388
-614 9386
-622 9378
-624 93...

output:

1

result:

ok 1 number(s): "1"

Test #78:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

500
6426 -6946
6448 -6925
6471 -6903
6495 -6880
6520 -6856
6546 -6831
6573 -6805
6660 -6721
6691 -6691
6692 -6690
6722 -6659
6751 -6629
6779 -6600
6832 -6545
6881 -6494
6904 -6470
6947 -6425
6967 -6404
6986 -6384
7004 -6365
7021 -6347
7037 -6330
7052 -6314
7081 -6283
7122 -6239
7160 -6198
7172 -6185...

output:

1

result:

ok 1 number(s): "1"

Test #79:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

2000
-4 -6500
-3 -7000
0 -8000
1 -8000
4 -7000
5 -6500
6 -6000
7 -5000
8 -3000
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
9 10
9 11
9 12
9 13
9 14
9 15
9 16
9 17
9 18
9 19
9 20
9 21
9 22
9 23
9 24
9 25
9 26
9 27
9 28
9 29
9 30
9 31
9 32
9 33
9 34
9 35
9 36
9 37
9 38
9 39
9 40
9 41
9 42
9 43
9 44
9 45
9...

output:

1

result:

ok 1 number(s): "1"

Test #80:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

835
-750 -9935
-731 -9937
-702 -9940
-692 -9941
-661 -9944
-640 -9946
-608 -9949
-597 -9950
-574 -9952
-562 -9953
-537 -9955
-524 -9956
-497 -9958
-483 -9959
-454 -9961
-439 -9962
-408 -9964
-392 -9965
-375 -9966
-357 -9967
-338 -9968
-318 -9969
-297 -9970
-275 -9971
-252 -9972
-228 -9973
-203 -9974...

output:

1

result:

ok 1 number(s): "1"

Test #81:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

2000
-5967 6
-5959 6
-5940 6
-5912 6
-5882 6
-5881 6
-5879 6
-5871 6
-5849 6
-5829 6
-5817 6
-5810 6
-5804 6
-5799 6
-5794 6
-5793 6
-5770 6
-5759 6
-5752 6
-5707 6
-5705 6
-5686 6
-5670 6
-5651 6
-5633 6
-5627 6
-5622 6
-5618 6
-5609 6
-5601 6
-5575 6
-5571 6
-5528 6
-5527 6
-5501 6
-5487 6
-5479 6...

output:

1

result:

ok 1 number(s): "1"

Test #82:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

1004
1000 9
999 9
998 9
997 9
996 9
995 9
994 9
993 9
992 9
991 9
990 9
989 9
988 9
987 9
986 9
985 9
984 9
983 9
982 9
981 9
980 9
979 9
978 9
977 9
976 9
975 9
974 9
973 9
972 9
971 9
970 9
969 9
968 9
967 9
966 9
965 9
964 9
963 9
962 9
961 9
960 9
959 9
958 9
957 9
956 9
955 9
954 9
953 9
952 9
...

output:

1

result:

ok 1 number(s): "1"

Test #83:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

183
-4 3
-8 2
-7 2
-7 1
-8 1
-12 0
-6 0
-6 1
-4 1
-5 0
0 0
-3 1
0 1
-6 2
-3 2
-2 3
-2 2
-1 3
-1 2
0 2
0 12
-1 12
0 13
0 15
-1 13
-1 14
0 16
-3 16
-1 15
-3 13
-3 14
-4 13
-3 15
-2 15
-4 16
-8 16
-6 15
-4 15
-4 14
-5 12
-5 13
-6 12
-8 12
-7 13
-8 13
-9 12
-9 13
-7 14
-8 14
-8 15
-6 14
-6 13
-5 14
-9 1...

output:

16

result:

ok 1 number(s): "16"

Test #84:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

183
-3 -4
-2 -8
-2 -7
-1 -7
-1 -8
0 -12
0 -6
-1 -6
-1 -4
0 -5
0 0
-1 -3
-1 0
-2 -6
-2 -3
-3 -2
-2 -2
-3 -1
-2 -1
-2 0
-12 0
-12 -1
-13 0
-15 0
-13 -1
-14 -1
-16 0
-16 -3
-15 -1
-13 -3
-14 -3
-13 -4
-15 -3
-15 -2
-16 -4
-16 -8
-15 -6
-15 -4
-14 -4
-12 -5
-13 -5
-12 -6
-12 -8
-13 -7
-13 -8
-12 -9
-13 ...

output:

20

result:

ok 1 number(s): "20"

Test #85:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

183
4 -3
8 -2
7 -2
7 -1
8 -1
12 0
6 0
6 -1
4 -1
5 0
0 0
3 -1
0 -1
6 -2
3 -2
2 -3
2 -2
1 -3
1 -2
0 -2
0 -12
1 -12
0 -13
0 -15
1 -13
1 -14
0 -16
3 -16
1 -15
3 -13
3 -14
4 -13
3 -15
2 -15
4 -16
8 -16
6 -15
4 -15
4 -14
5 -12
5 -13
6 -12
8 -12
7 -13
8 -13
9 -12
9 -13
7 -14
8 -14
8 -15
6 -14
6 -13
5 -14
9...

output:

19

result:

ok 1 number(s): "19"

Test #86:

score: 0
Accepted
time: 1ms
memory: 3632kb

input:

183
3 4
2 8
2 7
1 7
1 8
0 12
0 6
1 6
1 4
0 5
0 0
1 3
1 0
2 6
2 3
3 2
2 2
3 1
2 1
2 0
12 0
12 1
13 0
15 0
13 1
14 1
16 0
16 3
15 1
13 3
14 3
13 4
15 3
15 2
16 4
16 8
15 6
15 4
14 4
12 5
13 5
12 6
12 8
13 7
13 8
12 9
13 9
14 7
14 8
15 8
14 6
13 6
14 5
16 9
16 10
15 12
16 11
16 16
12 16
13 15
13 14
14 ...

output:

21

result:

ok 1 number(s): "21"

Test #87:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

195
-11 14
-11 13
-10 13
-9 14
-7 14
-10 15
-8 15
-6 14
-7 13
-9 13
-11 12
-12 12
-12 11
-13 11
-12 10
-13 10
-14 9
-12 9
-14 8
-15 7
-15 6
-13 8
-13 7
-12 8
-11 7
-10 8
-9 8
-12 6
-12 7
-13 6
-14 4
-14 6
-15 5
-16 8
-16 5
-15 4
-16 4
-16 0
-15 0
-15 3
-14 1
-13 1
-14 0
-11 0
-12 1
-9 1
-8 2
-8 1
-1...

output:

20

result:

ok 1 number(s): "20"

Test #88:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

195
-14 -11
-13 -11
-13 -10
-14 -9
-14 -7
-15 -10
-15 -8
-14 -6
-13 -7
-13 -9
-12 -11
-12 -12
-11 -12
-11 -13
-10 -12
-10 -13
-9 -14
-9 -12
-8 -14
-7 -15
-6 -15
-8 -13
-7 -13
-8 -12
-7 -11
-8 -10
-8 -9
-6 -12
-7 -12
-6 -13
-4 -14
-6 -14
-5 -15
-8 -16
-5 -16
-4 -15
-4 -16
0 -16
0 -15
-3 -15
-1 -14
-1...

output:

20

result:

ok 1 number(s): "20"

Test #89:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

195
11 -14
11 -13
10 -13
9 -14
7 -14
10 -15
8 -15
6 -14
7 -13
9 -13
11 -12
12 -12
12 -11
13 -11
12 -10
13 -10
14 -9
12 -9
14 -8
15 -7
15 -6
13 -8
13 -7
12 -8
11 -7
10 -8
9 -8
12 -6
12 -7
13 -6
14 -4
14 -6
15 -5
16 -8
16 -5
15 -4
16 -4
16 0
15 0
15 -3
14 -1
13 -1
14 0
11 0
12 -1
9 -1
8 -2
8 -1
10 0
2...

output:

19

result:

ok 1 number(s): "19"

Test #90:

score: 0
Accepted
time: 0ms
memory: 3448kb

input:

195
14 11
13 11
13 10
14 9
14 7
15 10
15 8
14 6
13 7
13 9
12 11
12 12
11 12
11 13
10 12
10 13
9 14
9 12
8 14
7 15
6 15
8 13
7 13
8 12
7 11
8 10
8 9
6 12
7 12
6 13
4 14
6 14
5 15
8 16
5 16
4 15
4 16
0 16
0 15
3 15
1 14
1 13
0 14
0 11
1 12
1 9
2 8
1 8
0 10
0 2
1 2
2 1
0 1
0 0
12 0
10 1
11 1
10 2
7 2
6...

output:

14

result:

ok 1 number(s): "14"

Test #91:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

186
-16 13
-15 12
-14 12
-15 13
-15 15
-14 15
-14 14
-13 13
-13 14
-12 14
-12 13
-13 12
-14 13
-13 11
-13 9
-14 8
-14 11
-15 11
-16 12
-16 6
-15 10
-15 7
-16 5
-16 2
-15 5
-15 6
-14 7
-14 6
-15 4
-15 3
-14 4
-13 4
-11 2
-14 1
-15 1
-12 2
-14 2
-13 3
-14 3
-16 1
-16 0
-8 0
-10 1
-13 1
-7 2
-10 2
-11 ...

output:

21

result:

ok 1 number(s): "21"

Test #92:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

186
-13 -16
-12 -15
-12 -14
-13 -15
-15 -15
-15 -14
-14 -14
-13 -13
-14 -13
-14 -12
-13 -12
-12 -13
-13 -14
-11 -13
-9 -13
-8 -14
-11 -14
-11 -15
-12 -16
-6 -16
-10 -15
-7 -15
-5 -16
-2 -16
-5 -15
-6 -15
-7 -14
-6 -14
-4 -15
-3 -15
-4 -14
-4 -13
-2 -11
-1 -14
-1 -15
-2 -12
-2 -14
-3 -13
-3 -14
-1 -1...

output:

16

result:

ok 1 number(s): "16"

Test #93:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

186
16 -13
15 -12
14 -12
15 -13
15 -15
14 -15
14 -14
13 -13
13 -14
12 -14
12 -13
13 -12
14 -13
13 -11
13 -9
14 -8
14 -11
15 -11
16 -12
16 -6
15 -10
15 -7
16 -5
16 -2
15 -5
15 -6
14 -7
14 -6
15 -4
15 -3
14 -4
13 -4
11 -2
14 -1
15 -1
12 -2
14 -2
13 -3
14 -3
16 -1
16 0
8 0
10 -1
13 -1
7 -2
10 -2
11 -3
...

output:

17

result:

ok 1 number(s): "17"

Test #94:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

186
13 16
12 15
12 14
13 15
15 15
15 14
14 14
13 13
14 13
14 12
13 12
12 13
13 14
11 13
9 13
8 14
11 14
11 15
12 16
6 16
10 15
7 15
5 16
2 16
5 15
6 15
7 14
6 14
4 15
3 15
4 14
4 13
2 11
1 14
1 15
2 12
2 14
3 13
3 14
1 16
0 16
0 8
1 10
1 13
2 7
2 10
3 11
3 9
5 11
6 11
7 12
5 12
4 11
4 12
5 13
6 13
5...

output:

23

result:

ok 1 number(s): "23"

Test #95:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

191
-3 2
-2 2
-2 1
-1 0
-2 3
-4 5
-3 5
-2 4
-2 6
-4 8
-4 9
-5 9
-5 8
-4 7
-6 7
-5 6
-3 6
-5 5
-4 4
-4 3
-6 5
-6 6
-7 6
-9 8
-9 7
-5 3
-5 2
-7 4
-6 2
-6 1
-7 1
-7 2
-8 2
-10 1
-9 2
-11 1
-9 3
-10 4
-10 3
-11 2
-11 3
-12 3
-12 1
-13 1
-13 3
-14 1
-15 1
-14 2
-15 3
-15 4
-14 3
-13 4
-13 6
-14 4
-14 5
-...

output:

19

result:

ok 1 number(s): "19"

Test #96:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

191
-2 -3
-2 -2
-1 -2
0 -1
-3 -2
-5 -4
-5 -3
-4 -2
-6 -2
-8 -4
-9 -4
-9 -5
-8 -5
-7 -4
-7 -6
-6 -5
-6 -3
-5 -5
-4 -4
-3 -4
-5 -6
-6 -6
-6 -7
-8 -9
-7 -9
-3 -5
-2 -5
-4 -7
-2 -6
-1 -6
-1 -7
-2 -7
-2 -8
-1 -10
-2 -9
-1 -11
-3 -9
-4 -10
-3 -10
-2 -11
-3 -11
-3 -12
-1 -12
-1 -13
-3 -13
-1 -14
-1 -15
-2 ...

output:

14

result:

ok 1 number(s): "14"

Test #97:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

191
3 -2
2 -2
2 -1
1 0
2 -3
4 -5
3 -5
2 -4
2 -6
4 -8
4 -9
5 -9
5 -8
4 -7
6 -7
5 -6
3 -6
5 -5
4 -4
4 -3
6 -5
6 -6
7 -6
9 -8
9 -7
5 -3
5 -2
7 -4
6 -2
6 -1
7 -1
7 -2
8 -2
10 -1
9 -2
11 -1
9 -3
10 -4
10 -3
11 -2
11 -3
12 -3
12 -1
13 -1
13 -3
14 -1
15 -1
14 -2
15 -3
15 -4
14 -3
13 -4
13 -6
14 -4
14 -5
13...

output:

19

result:

ok 1 number(s): "19"

Test #98:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

191
2 3
2 2
1 2
0 1
3 2
5 4
5 3
4 2
6 2
8 4
9 4
9 5
8 5
7 4
7 6
6 5
6 3
5 5
4 4
3 4
5 6
6 6
6 7
8 9
7 9
3 5
2 5
4 7
2 6
1 6
1 7
2 7
2 8
1 10
2 9
1 11
3 9
4 10
3 10
2 11
3 11
3 12
1 12
1 13
3 13
1 14
1 15
2 14
3 15
4 15
3 14
4 13
6 13
4 14
5 14
7 13
6 14
8 13
8 12
4 12
4 11
9 11
7 10
5 10
3 8
3 7
5 9...

output:

21

result:

ok 1 number(s): "21"

Test #99:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

1759
19 19
20 21
20 20
21 21
21 20
22 20
23 19
24 17
24 18
25 18
25 17
27 18
29 18
30 19
30 22
29 20
26 20
29 19
28 19
26 18
24 19
27 19
24 20
23 20
21 22
23 22
23 21
24 21
25 20
25 21
26 21
25 22
24 22
25 23
25 24
24 23
20 23
22 24
20 24
22 25
19 25
19 27
21 28
22 29
24 29
23 28
24 28
25 29
24 30
2...

output:

158

result:

ok 1 number(s): "158"

Test #100:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

1717
26 39
27 41
25 41
26 43
23 43
24 42
24 41
23 39
21 40
23 40
23 41
22 41
23 42
22 42
22 44
24 44
24 45
19 45
21 44
20 44
21 43
20 43
20 42
19 42
19 44
15 45
18 45
23 46
26 46
26 45
25 45
25 44
26 44
27 45
28 45
27 44
28 44
28 43
27 43
26 42
30 42
29 43
31 43
33 44
31 44
33 45
30 44
29 44
32 45
3...

output:

155

result:

ok 1 number(s): "155"

Test #101:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

83
0 164
1 197
1 150
0 163
0 65
1 100
1 41
0 64
0 25
1 40
1 2
0 24
0 10
1 1
0 9
0 0
2 0
2 59
1 101
1 149
2 60
2 165
1 216
1 238
2 166
2 470
1 462
1 535
2 471
2 771
1 651
1 714
2 772
2 861
1 831
1 900
2 862
2 907
1 901
1 911
2 908
2 957
1 912
1 983
2 958
2 999
0 999
0 997
1 998
1 987
0 996
0 993
1 98...

output:

13

result:

ok 1 number(s): "13"

Test #102:

score: 0
Accepted
time: 0ms
memory: 3448kb

input:

97
522 0
474 1
543 1
523 0
670 0
544 1
652 1
671 0
736 0
653 1
668 1
737 0
758 0
723 1
752 1
759 0
831 0
753 1
804 1
832 0
875 0
805 1
845 1
876 0
915 0
846 1
957 1
916 0
981 0
975 1
985 1
982 0
986 0
986 1
992 1
987 0
999 0
998 1
999 1
999 2
997 1
993 1
998 2
969 2
974 1
958 1
968 2
813 2
722 1
684...

output:

14

result:

ok 1 number(s): "14"

Test #103:

score: 0
Accepted
time: 1ms
memory: 3496kb

input:

171
3 40
2 61
2 48
1 53
1 56
2 62
2 71
1 57
1 67
2 102
2 72
3 41
3 146
2 161
2 193
3 147
3 165
2 194
2 219
1 257
1 298
2 220
2 249
3 166
3 196
2 299
2 250
1 380
1 413
2 426
2 300
3 197
3 304
2 427
2 529
3 305
3 547
2 565
2 530
1 414
1 453
2 566
2 572
1 454
1 586
2 662
2 573
3 548
3 707
2 663
2 726
3...

output:

27

result:

ok 1 number(s): "27"

Test #104:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

169
292 1
223 0
460 0
447 1
496 1
461 0
510 0
497 1
528 1
511 0
650 0
632 1
614 1
573 2
602 2
633 1
653 1
651 0
841 0
837 1
846 1
806 2
869 2
847 1
872 1
842 0
899 0
873 1
917 1
900 0
912 0
928 1
918 1
901 2
956 2
929 1
995 1
913 0
999 0
996 1
995 2
997 2
997 1
999 1
999 2
998 2
999 3
996 3
994 2
99...

output:

15

result:

ok 1 number(s): "15"

Test #105:

score: 0
Accepted
time: 1ms
memory: 3552kb

input:

2000
3316 4595
4152 4662
4692 5559
4805 5785
4445 6103
3936 6224
4153 6375
4382 6574
4721 6189
6281 6497
5858 5760
6308 5713
6729 5979
6197 6721
6374 7103
6205 6871
5757 6512
5087 6488
5842 7042
4897 7761
5110 7282
4851 6381
4809 6715
4810 7013
4808 7440
3482 7551
3746 7800
3112 7468
3479 7039
3347 ...

output:

217

result:

ok 1 number(s): "217"

Test #106:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

2000
-2720 -1363
-2774 1491
-2754 1837
-2751 4697
-2756 8857
-2915 9905
-2524 9530
-2774 9694
-2604 8757
-2541 1908
-2608 1807
-2650 3360
-2663 8316
-2640 -7601
-2644 -5216
-2672 -7637
-2673 8295
-2680 3413
-2707 9287
-2682 -5749
-2678 -8779
-3156 -9988
861 -9952
1509 -9829
1199 -9503
1342 -8775
140...

output:

209

result:

ok 1 number(s): "209"

Test #107:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

1999
389 180
389 168
363 119
380 137
375 139
451 124
404 140
453 147
541 133
492 206
483 188
499 256
572 138
571 199
608 165
573 25
554 45
546 72
502 54
520 83
539 130
459 83
437 103
454 57
428 60
439 77
420 74
421 83
422 108
418 106
396 124
406 82
418 59
372 88
356 52
363 35
402 46
422 52
420 20
41...

output:

233

result:

ok 1 number(s): "233"

Test #108:

score: 0
Accepted
time: 1ms
memory: 3696kb

input:

1998
740 -650
753 -696
719 -663
683 -565
593 -539
586 -446
648 -415
713 -447
639 -331
566 -351
523 -297
575 -264
616 -286
541 -227
462 -324
460 -370
479 -380
585 -430
566 -427
510 -401
585 -516
489 -435
384 -380
423 -442
478 -536
379 -415
313 -361
325 -318
263 -421
303 -482
306 -512
287 -516
259 -50...

output:

216

result:

ok 1 number(s): "216"

Test #109:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

2000
8596 -48
7794 130
7241 379
7079 -51
6516 146
6126 523
5542 402
6080 -117
6102 -221
5556 -714
6301 -699
6527 -264
6588 -1964
6638 -1591
6787 -1210
6613 -2173
7031 -1363
7158 -615
7338 -1411
7520 -1518
7412 -797
7297 -575
8579 -546
8285 -1447
8873 -845
9229 -2075
9066 -1543
8703 -2732
8751 -1218
...

output:

211

result:

ok 1 number(s): "211"

Test #110:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

1982
-2352 -9719
-2336 -9723
-2233 -9748
-2030 -9792
-2005 -9797
-2000 -9798
-1923 -9813
-1827 -9832
-1630 -9866
-1599 -9871
-1479 -9890
-1468 -9892
-1397 -9902
-1250 -9922
-1424 -9898
-1199 -9928
-950 -9955
-882 -9961
-832 -9965
-837 -9965
-805 -9968
-789 -9969
-808 -9967
-750 -9972
-747 -9972
-625...

output:

170

result:

ok 1 number(s): "170"

Test #111:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

2000
-9971 -8103
-9974 -7669
-9979 -8429
-9980 -8596
-9967 -6301
-9975 -6339
-9974 -5348
-9978 -4930
-9980 -5634
-9980 -5589
-9987 -5997
-9984 -5767
-9984 -5190
-9980 -5139
-9978 -4211
-9979 -4169
-9971 -2544
-9967 -2727
-9969 -2352
-9962 -1860
-9957 -579
-9963 -1432
-9962 -968
-9962 -674
-9965 -108...

output:

208

result:

ok 1 number(s): "208"