QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#791258#5443. Security at Museumsskip2004AC ✓47ms4304kbC++204.6kb2024-11-28 17:44:012024-11-28 17:44:07

Judging History

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

  • [2024-11-28 17:44:07]
  • 评测
  • 测评结果:AC
  • 用时:47ms
  • 内存:4304kb
  • [2024-11-28 17:44:01]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 205;
const int mod = 998244353;
void add(int & x, int y) {
	if((x += y) >= mod) {
		x -= mod;
	}
}
using ll = long long;
int n;
ll sgn(ll x) {
	return x < 0 ? -1 : x > 0;
}
struct vec2 {
	int x, y;
	ll norm() {
		return (ll) x * x + (ll) y * y;
	}
	vec2() {}
	vec2(int a, int b) : x(a), y(b) {}
} a[N];
vec2 operator + (vec2 x, vec2 y) {
	return vec2(x.x + y.x, x.y + y.y);
}
vec2 operator - (vec2 x, vec2 y) {
	return vec2(x.x - y.x, x.y - y.y);
}
ll operator * (vec2 x, vec2 y) {
	return (ll) x.x * y.y - (ll) x.y * y.x;
}
ll operator % (vec2 x, vec2 y) {
	return (ll) x.x * y.x + (ll) x.y * y.y;
}
bool operator == (vec2 x, vec2 y) { 
	return x.x == y.x && x.y == y.y;
}
struct seg {
	vec2 x, y;
} b[N];
int e[N][N];
bool test(vec2 x, vec2 y, vec2 z) {
	return (y - x) * (z - x) == 0;
}
void link(int x, int y) {
	if(e[x][y]) return ;
	e[x][y] = 1;
	e[y][x] = 1;
	for(int i = 1;i <= n;++i) {
		if(!e[y][i] && e[x][i] && e[x][y] && test(a[i], a[x], a[y])) {
			link(i, y);
		}
	}
	std::swap(x, y);
	for(int i = 1;i <= n;++i) {
		if(!e[y][i] && e[x][i] && e[x][y] && test(a[i], a[x], a[y])) {
			link(i, y);
		}
	}
}
int ccw(vec2 a, vec2 b, vec2 c) {
	int sign = sgn((b - a) * (c - a));
	if(sign == 0) {
		if(sgn((b - a) % (c - a)) == -1) {
			return 2;
		}
		if((c - a).norm() > (b - a).norm()) {
			return -2;
		}
	}
	return sign;
}
int is_isc(const seg & x, const seg & y) {
	return
		ccw(x.x, x.y, y.x) * ccw(x.x, x.y, y.y) <= 0 &&
		ccw(y.x, y.y, x.x) * ccw(y.x, y.y, x.y) <= 0;
}
int half(const vec2 & x) {
	return x.y < 0 || (x.y == 0 && x.x <= 0);
}
bool cmp(vec2 A, vec2 B) {
	if(half(A) != half(B)) return half(B);
	return A * B > 0;
}
bool cmp_eq(vec2 A, vec2 B) {
	return half(A) == half(B) && A * B == 0;
}
struct pr { // 凸包 DP
	int i, j;
	vec2 get() const {
		return a[j] - a[i];
	}
};
bool cmpseg(pr x, pr y) {
	vec2 A = x.get(), B = y.get();
	if(!cmp(A, B) && !cmp(B, A)) {
		return a[x.i] % A < a[y.i] % A;
	}
	return cmp(A, B);
}
// 判断 A, B, C 三个向量是否是逆时针顺序
// 如果是,返回 1
// 如果 (A, B), (C, B) 同方向共线,返回 -1
// 如果是顺时针,返回 0
bool cmp_ct(vec2 A, vec2 B, vec2 C) {
	if(cmp_eq(A, B)) return -1;
	if(cmp_eq(C, B)) return -1;
	if(cmp(A, B)) {
		return cmp(B, C) || cmp(C, A);
	} else {
		return cmp(B, C) && cmp(C, A);
	}
}
bool valid(int i, int j) {
	vec2 dir = a[j] - a[i];
	vec2 A = vec2(a[i % n + 1] - a[i]);
	vec2 B = vec2(a[i == 1 ? n : i - 1] - a[i]);
	return cmp_ct(A, dir, B) == 1;
}
int dp[N][N];
int f[N];
int g[N];
using u64 = unsigned long long;
int pow(int a, int b, int ans = 1) {
	for(;b;b >>= 1, a = (u64) a * a % mod) {
		if(b & 1) ans = (u64) ans * a % mod;
	}
	return ans;
}
void init() {
	for(int i = 1;i <= n;++i) {
		f[i] = (pow(2, i) + mod - i - 1) % mod;
		for(int j = 2;j <= i;++j) {
			g[i ] = (g[i] + (u64) (i - j + 1) * pow(2, (j - 2) * 2)) % mod;
		}
	}
}
int pb() {
	int ans = 0;
	for(int i = 1;i <= n;++i) {
		for(int j = 1;j < i;++j) if(e[i][j]) {
			std::vector<int> set = {i, j};
			for(int k = 1;k <= n;++k) if(k != i && k != j) {
				if(e[i][k] && test(a[i], a[j], a[k])) {
					set.push_back(k);
				}
			}
			for(int x : set) for(int y : set) {
				e[x][y] = e[y][x] = 0;
			}
			ans = (ans + mod - g[set.size()]) % mod;
			ans = (ans + f[set.size()]) % mod;
		}
	}
	return ans;
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;++i) {
		cin >> a[i].x >> a[i].y;
		e[i][i] = 1;
	}
	for(int i = 1;i <= n;++i) {
		b[i].x = a[i];
		b[i].y = a[i % n + 1];
		link(i, i % n + 1);
	}
	for(int i = 1;i <= n;++i) {
		for(int j = i + 2;j <= n;++j) {
			if(!e[i][j]) {
				if(valid(i, j) && valid(j, i)) {
					int good = 1;
					for(int k = 1;k <= n;++k) {
						int pk = k % n + 1;
						if(i == k || i == pk || j == k || j == pk) {
							continue;
						}
						if(is_isc(seg{a[i], a[j]}, b[k])) {
							good = 0;
							break;
						}
					}
					if(good) {
						link(i, j);
					}
				}
			}
		}
	}
	std::vector<pr> v;
	for(int i = 1;i <= n;++i) {
		for(int j = 1;j <= n;++j) if(i != j && e[i][j]) {
			v.push_back({i, j});
		}
	}
	sort(v.begin(), v.end(), cmpseg);
	int ans = mod - n;
	for(int i = 1;i <= n;++i) {
		dp[i][i] = 1;
	}
	for(auto [x, y] : v) {
		for(int i = 1;i <= n;++i) {
			add(dp[y][i], dp[x][i]);
		}
	}
	init();
	for(int i = 1;i <= n;++i) {
		add(ans, dp[i][i]);
	}
	ans = (ans + pb()) % mod;
	cout << ans << '\n';
}

详细

Test #1:

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

input:

7
0 20
40 0
40 20
70 50
50 70
30 50
0 50

output:

56

result:

ok 1 number(s): "56"

Test #2:

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

input:

3
0 2022
-2022 -2022
2022 0

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

3
4 0
0 3
0 0

output:

4

result:

ok 1 number(s): "4"

Test #4:

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

input:

3
-10 0
10 0
0 18

output:

4

result:

ok 1 number(s): "4"

Test #5:

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

input:

4
0 0
-10 0
-10 -10
0 -10

output:

11

result:

ok 1 number(s): "11"

Test #6:

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

input:

4
-100 0
0 -100
100 0
0 100

output:

11

result:

ok 1 number(s): "11"

Test #7:

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

input:

4
0 0
10 5
20 0
10 10

output:

7

result:

ok 1 number(s): "7"

Test #8:

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

input:

4
0 0
20 0
30 10
10 10

output:

11

result:

ok 1 number(s): "11"

Test #9:

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

input:

4
-100 -10
100 -10
100 10
-100 10

output:

11

result:

ok 1 number(s): "11"

Test #10:

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

input:

4
0 0
100 0
60 30
0 30

output:

11

result:

ok 1 number(s): "11"

Test #11:

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

input:

4
0 0
100 0
60 30
40 30

output:

11

result:

ok 1 number(s): "11"

Test #12:

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

input:

7
0 0
10 10
20 0
30 11
20 22
10 11
0 22

output:

44

result:

ok 1 number(s): "44"

Test #13:

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

input:

10
0 0
10 10
20 0
30 10
40 0
40 21
30 11
20 21
10 11
0 21

output:

93

result:

ok 1 number(s): "93"

Test #14:

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

input:

7
0 0
50 50
80 20
110 50
70 90
40 60
0 100

output:

44

result:

ok 1 number(s): "44"

Test #15:

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

input:

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

output:

407

result:

ok 1 number(s): "407"

Test #16:

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

input:

12
0 0
400 0
400 500
0 500
0 200
200 200
200 300
100 300
100 400
300 400
300 100
0 100

output:

51

result:

ok 1 number(s): "51"

Test #17:

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

input:

10
0 500
-10 20
-350 350
-20 0
-350 -350
0 -20
350 -350
20 0
350 350
10 20

output:

93

result:

ok 1 number(s): "93"

Test #18:

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

input:

16
0 0
10 -5
20 0
30 15
40 0
45 10
40 20
25 30
40 40
30 45
20 40
10 25
0 40
-5 30
0 20
15 10

output:

247

result:

ok 1 number(s): "247"

Test #19:

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

input:

8
100 90
90 100
-90 100
-100 90
-100 -90
-90 -100
90 -100
100 -90

output:

247

result:

ok 1 number(s): "247"

Test #20:

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

input:

8
0 0
10 100
90 100
100 0
100 201
90 101
10 101
0 201

output:

31

result:

ok 1 number(s): "31"

Test #21:

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

input:

8
0 0
100 100
900 100
1000 0
1000 210
900 110
100 110
0 210

output:

31

result:

ok 1 number(s): "31"

Test #22:

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

input:

3
1000000 -1000000
1000000 1000000
-1000000 -1000000

output:

4

result:

ok 1 number(s): "4"

Test #23:

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

input:

4
1000000 -1000000
1000000 1000000
1 0
-1000000 -1000000

output:

7

result:

ok 1 number(s): "7"

Test #24:

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

input:

4
1000000 -1000000
1000000 1000000
0 1
-1000000 -1000000

output:

11

result:

ok 1 number(s): "11"

Test #25:

score: 0
Accepted
time: 46ms
memory: 4304kb

input:

200
-28269 899556
-52917 898443
-82904 896173
-112799 892903
-139901 889060
-167758 884227
-196328 878325
-220331 872613
-248497 865014
-277258 856229
-302321 847703
-331311 836799
-354953 827048
-381571 815109
-407788 802314
-431209 789973
-455810 776039
-479961 761338
-503639 745887
-529006 728115...

output:

982924531

result:

ok 1 number(s): "982924531"

Test #26:

score: 0
Accepted
time: 47ms
memory: 3964kb

input:

200
-28269 899556
-52917 898443
-82904 896173
-112799 892903
-139901 889060
-167758 884227
-196328 878325
-220331 872613
-248497 865014
-277258 856229
-302321 847703
-331311 836799
-354953 827048
-381571 815109
-407788 802314
-431209 789973
-455810 776039
-479961 761338
-503639 745887
-529006 728115...

output:

491462169

result:

ok 1 number(s): "491462169"

Test #27:

score: 0
Accepted
time: 8ms
memory: 4288kb

input:

200
-1000000 0
-984589 0
-959090 -1000000
-939997 0
-920698 -1000000
-903689 0
-878269 -1000000
-856526 0
-835872 -1000000
-824921 0
-802874 -1000000
-775273 0
-762503 -1000000
-736648 0
-723628 -1000000
-700062 0
-677324 -1000000
-655520 0
-638093 -1000000
-616069 0
-596730 -1000000
-578522 0
-5610...

output:

766756066

result:

ok 1 number(s): "766756066"

Test #28:

score: 0
Accepted
time: 11ms
memory: 4100kb

input:

200
-982632 0
-969103 -1000000
-940842 0
-921682 0
-906001 -1000000
-879789 0
-865042 0
-845192 -1000000
-816404 0
-802606 0
-787373 -1000000
-753645 0
-737956 0
-725228 -1000000
-692298 0
-681026 0
-651636 -1000000
-636348 0
-619790 0
-587407 -1000000
-573321 0
-558772 0
-527808 -1000000
-513494 0
...

output:

399992829

result:

ok 1 number(s): "399992829"

Test #29:

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

input:

7
30 0
30 20
60 40
90 40
90 60
20 50
0 0

output:

40

result:

ok 1 number(s): "40"

Test #30:

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

input:

9
30 0
30 20
20 30
50 50
60 40
90 40
90 60
20 50
0 0

output:

30

result:

ok 1 number(s): "30"

Test #31:

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

input:

10
0 0
400 0
400 200
300 200
300 100
100 100
100 300
400 300
400 400
0 400

output:

41

result:

ok 1 number(s): "41"

Test #32:

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

input:

10
0 -400
400 -400
400 -300
100 -300
100 -100
300 -100
300 -200
400 -200
400 0
0 0

output:

41

result:

ok 1 number(s): "41"

Test #33:

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

input:

20
-2 11
-6 3
-4 2
-1 8
9 3
3 -9
-5 -5
-4 -3
2 -6
6 2
0 5
-2 1
0 0
1 2
3 1
1 -3
-5 0
-8 -6
4 -12
12 4

output:

91

result:

ok 1 number(s): "91"

Test #34:

score: 0
Accepted
time: 4ms
memory: 3856kb

input:

200
-153811 101954
-110538 -13951
-21156 16822
20793 -224637
-105318 -28386
-184845 -25122
-55966 -252174
-65073 -240349
-402588 -55614
-319429 351875
-479382 92012
-213699 555429
112299 348899
687998 510477
379335 468944
157461 420548
102219 458523
148907 488400
610913 530181
430304 566961
821268 5...

output:

1687

result:

ok 1 number(s): "1687"

Test #35:

score: 0
Accepted
time: 4ms
memory: 4012kb

input:

200
122301 113556
338694 233402
368238 131577
446030 331311
535103 535679
781548 843294
666909 875595
442356 427784
374568 306449
-26086 6336
356963 370926
75420 132096
109676 185484
392958 553349
511233 697425
-105084 -25122
16287 361251
338613 501111
251648 493356
589628 908975
16500 972309
535022...

output:

1663

result:

ok 1 number(s): "1663"

Test #36:

score: 0
Accepted
time: 5ms
memory: 4144kb

input:

200
421640 547713
650121 928769
547442 928833
346206 886544
-452730 992357
102138 855965
111368 905793
366936 808814
97664 687998
306486 711903
22692 663762
-57963 885504
-55792 734234
-463485 989088
-157192 737144
-241500 603149
-444462 699033
-203932 580725
37067 568415
339672 708146
497484 744522...

output:

1599

result:

ok 1 number(s): "1599"

Test #37:

score: 0
Accepted
time: 4ms
memory: 3912kb

input:

200
207543 18138
233654 136908
700845 -843115
765038 -961705
480771 -367522
784833 -913671
931941 -853932
718884 -558630
197457 373259
426012 6606
359594 164931
795933 -587514
362999 173610
635496 -231358
517028 -17575
653370 -224637
779784 -468309
814878 -651810
970226 -830284
897312 -690219
653588...

output:

1403

result:

ok 1 number(s): "1403"

Test #38:

score: 0
Accepted
time: 4ms
memory: 3920kb

input:

200
384246 119904
515880 90069
537210 144074
706626 62156
434349 603996
378143 465476
443127 317247
164931 198306
533444 341568
239054 104826
37271 27579
161283 99692
-13462 22109
497481 748134
753303 786567
441458 667358
736625 725172
466416 609863
638721 590361
679778 436017
624801 526664
704712 1...

output:

1703

result:

ok 1 number(s): "1703"

Test #39:

score: 0
Accepted
time: 4ms
memory: 4016kb

input:

200
290300 170277
240567 128495
339132 87891
177572 360968
480771 164259
512115 17961
405629 5648
333267 87849
346164 -61209
737469 -277905
699884 -331989
552159 -233661
67764 13977
51210 -31561
624573 -303696
365547 -415143
596037 -320155
382416 -471408
455414 -430867
473946 -409309
653883 -416259
...

output:

1723

result:

ok 1 number(s): "1723"

Test #40:

score: 0
Accepted
time: 4ms
memory: 3976kb

input:

200
-55665 353610
-95883 490124
132390 -66873
58841 248211
516981 -547989
507597 -169864
509958 -216196
522693 -268425
681047 -280795
494694 -143556
266337 -45390
313914 -52921
223239 1950
194649 346206
384276 367670
369288 321381
762722 -204108
497747 152082
716706 205593
526883 280884
795998 34640...

output:

1959

result:

ok 1 number(s): "1959"

Test #41:

score: 0
Accepted
time: 4ms
memory: 4176kb

input:

200
283343 271859
383730 322703
365793 322247
450695 405629
434937 311613
486618 479943
358449 -12483
67130 -122775
416790 227442
-16551 -180451
295266 -315165
383364 28503
502124 440735
527090 528342
456162 243552
444408 -165328
648036 -459271
561377 -12972
539900 87975
597287 63161
566952 304059
7...

output:

1703

result:

ok 1 number(s): "1703"

Test #42:

score: 0
Accepted
time: 4ms
memory: 3856kb

input:

200
5009 71481
-20981 20885
-12 -30222
-99838 189696
103887 126708
351540 380079
242496 299244
527678 785484
336098 539408
101865 137745
64338 267396
147075 359897
524 197672
520671 794027
-45390 774477
408812 806877
32813 864956
-594379 939110
-400881 862851
-841240 825276
-623754 795456
-233265 84...

output:

1579

result:

ok 1 number(s): "1579"

Test #43:

score: 0
Accepted
time: 5ms
memory: 3860kb

input:

200
635384 485892
765764 574319
336258 334347
465048 520794
519375 558921
682283 607704
982737 801953
564318 664179
209807 405618
419262 582690
-7986 577806
-441678 673641
171933 603149
261948 582564
129839 653445
374771 807498
499641 893376
916239 999597
-190753 742980
162081 984042
-325008 701442
...

output:

1731

result:

ok 1 number(s): "1731"

Test #44:

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

input:

6
0 0
110828 157796
232685 157796
232685 331295
214662 305634
0 305634

output:

29

result:

ok 1 number(s): "29"

Test #45:

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

input:

10
0 0
110828 157796
233685 157796
233685 341295
232685 341295
232685 331295
214662 305634
-1000 305634
-1000 -10000
0 -10000

output:

49

result:

ok 1 number(s): "49"

Test #46:

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

input:

6
0 220492
-741872 220492
-750260 222985
-750260 205257
-690612 205257
0 0

output:

29

result:

ok 1 number(s): "29"

Test #47:

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

input:

10
0 -3000
10000 -3000
10000 220492
-741872 220492
-750260 222985
-750260 225985
-760260 225985
-760260 205257
-690612 205257
0 0

output:

49

result:

ok 1 number(s): "49"

Test #48:

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

input:

6
-999999 -1000000
1000000 999999
-999999 999999
-999999 -999999
-1000000 -999999
-1000000 -1000000

output:

25

result:

ok 1 number(s): "25"

Test #49:

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

input:

6
-999999 -1000000
-999999 -999999
1000000 -999999
1000000 999999
999998 999999
-1000000 -1000000

output:

17

result:

ok 1 number(s): "17"

Test #50:

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

input:

6
-999999 -1000000
-999998 -999999
1000000 -999999
1000000 999999
999998 999999
-1000000 -1000000

output:

33

result:

ok 1 number(s): "33"

Test #51:

score: 0
Accepted
time: 7ms
memory: 4084kb

input:

200
1000000 -999941
-999956 -999940
-998042 -997864
-998053 -997864
-994830 -994360
-994841 -994360
-990958 -990136
-990969 -990136
-983566 -982072
-983577 -982072
-978319 -976348
-978330 -976348
-976768 -974656
-976779 -974656
-975228 -972976
-975239 -972976
-973116 -970672
-973127 -970672
-972808 ...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #52:

score: 0
Accepted
time: 7ms
memory: 4032kb

input:

200
1000000 -998489
-999630 -998488
-992008 -959932
-992082 -959932
-989862 -948970
-989936 -948970
-989344 -946324
-989418 -946324
-978688 -891892
-978762 -891892
-967292 -833680
-967366 -833680
-966182 -828010
-966256 -828010
-965146 -822718
-965220 -822718
-964850 -821206
-964924 -821206
-964480 ...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #53:

score: 0
Accepted
time: 7ms
memory: 4032kb

input:

200
-1000000 999787
998030 999786
958630 978600
959024 978600
946810 972180
947204 972180
940112 968542
940506 968542
837278 912688
837672 912688
817972 902202
818366 902202
814426 900276
814820 900276
809698 897708
810092 897708
798272 891502
798666 891502
788028 885938
788422 885938
785270 884440
...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #54:

score: 0
Accepted
time: 7ms
memory: 4256kb

input:

200
-1000000 997586
999374 997585
897023 840127
897336 840127
789977 674941
790290 674941
783091 664315
783404 664315
759616 628090
759929 628090
708597 549361
708910 549361
704215 542599
704528 542599
702963 540667
703276 540667
700459 536803
700772 536803
699520 535354
699833 535354
624400 419434
...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #55:

score: 0
Accepted
time: 7ms
memory: 4088kb

input:

200
1000000 -999485
975920 -982198
965600 -974200
965256 -974200
964224 -973168
963880 -973168
962504 -971878
962160 -971878
961816 -971362
961472 -971362
961128 -970846
960784 -970846
948744 -961558
948400 -961558
931200 -948400
930856 -948400
906088 -929566
905744 -929566
881320 -910990
880976 -91...

output:

441250454

result:

ok 1 number(s): "441250454"

Test #56:

score: 0
Accepted
time: 7ms
memory: 4028kb

input:

200
1000000 -999175
975085 -976872
963760 -966134
963307 -966134
918460 -924834
918007 -924834
714157 -738571
713704 -738571
638959 -670013
638506 -670013
460477 -507291
460024 -507291
360364 -416018
359911 -416018
359458 -415192
359005 -415192
355381 -411475
354928 -411475
341338 -398672
340885 -39...

output:

441250454

result:

ok 1 number(s): "441250454"

Test #57:

score: 0
Accepted
time: 7ms
memory: 4292kb

input:

200
-1000000 998441
-996730 995710
-994441 992590
-994114 992590
-985285 981670
-984958 981670
-971878 965680
-971551 965680
-967627 960610
-967300 960610
-947026 936040
-946699 936040
-925771 910690
-925444 910690
-797587 757810
-797260 757810
-791374 750400
-791047 750400
-712240 656020
-711913 65...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #58:

score: 0
Accepted
time: 7ms
memory: 4096kb

input:

200
-1000000 998176
-999748 997810
-999496 996350
-999412 996350
-999160 994890
-999076 994890
-982360 921890
-982276 921890
-981352 917510
-981268 917510
-975136 890500
-975052 890500
-850144 347380
-850060 347380
-817216 204300
-817132 204300
-800920 133490
-800836 133490
-787816 76550
-787732 765...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #59:

score: 0
Accepted
time: 3ms
memory: 4032kb

input:

200
100000 -999633
239 -999632
3094 -999448
239 -999448
7467 -999264
239 -999264
4608 -998896
239 -998896
649 -998712
239 -998712
2980 -998528
239 -998528
1563 -998344
239 -998344
7731 -989788
239 -989788
744 -927504
239 -927504
2244 -838724
239 -838724
8203 -807628
239 -807628
4217 -780304
239 -780...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #60:

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

input:

4
-899998 -900000
0 0
450000 450001
449998 449999

output:

7

result:

ok 1 number(s): "7"

Test #61:

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

input:

4
-1000000 -1000000
0 -1
999999 999997
-1 0

output:

7

result:

ok 1 number(s): "7"

Test #62:

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

input:

5
1000000 -1000000
1000000 999999
999999 0
999999 999998
-1000000 -1000000

output:

10

result:

ok 1 number(s): "10"

Test #63:

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

input:

10
-800000 -799999
199991 199997
799987 799996
999985 999995
599988 599996
199990 199996
-200006 -200002
-600003 -600001
-800001 -800000
-1000000 -1000000

output:

73

result:

ok 1 number(s): "73"

Test #64:

score: 0
Accepted
time: 5ms
memory: 3924kb

input:

200
-677343 996088
-731021 806109
-703638 644867
-694433 455591
-698504 132249
-745640 -209598
-859170 -239875
-874703 -116547
-922684 -350844
-920583 296332
-867486 433468
-860134 490879
-849686 -2551
-813758 684881
-777869 965896
-905744 958941
-983905 544305
-996951 494366
-982454 -386675
-977004...

output:

5283

result:

ok 1 number(s): "5283"

Test #65:

score: 0
Accepted
time: 4ms
memory: 3908kb

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:

55064

result:

ok 1 number(s): "55064"

Test #66:

score: 0
Accepted
time: 4ms
memory: 4148kb

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:

5564

result:

ok 1 number(s): "5564"

Test #67:

score: 0
Accepted
time: 4ms
memory: 4012kb

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:

8148

result:

ok 1 number(s): "8148"

Test #68:

score: 0
Accepted
time: 2ms
memory: 3960kb

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:

9369

result:

ok 1 number(s): "9369"

Test #69:

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

input:

38
1 95
2 94
2 129
1 96
1 152
2 130
2 156
1 153
1 165
2 157
2 174
1 173
1 189
2 175
2 190
1 190
1 195
2 191
2 199
1 199
1 196
0 199
0 159
1 172
1 166
0 158
0 47
1 83
1 45
0 46
0 0
2 0
2 4
1 1
1 44
2 5
2 93
1 84

output:

263261

result:

ok 1 number(s): "263261"

Test #70:

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

input:

57
192 0
170 1
188 1
193 0
195 0
189 1
198 1
196 0
199 0
199 2
164 2
169 1
152 1
163 2
115 2
117 1
106 1
114 2
82 2
105 1
93 1
81 2
62 2
49 1
41 1
61 2
5 2
25 1
11 1
4 2
0 2
0 1
6 1
0 0
4 0
7 1
10 1
5 0
17 0
26 1
40 1
18 0
55 0
50 1
73 1
56 0
97 0
74 1
92 1
98 0
127 0
118 1
128 0
153 0
119 1
151 1
1...

output:

134218614

result:

ok 1 number(s): "134218614"

Test #71:

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

input:

71
2 970
1 939
1 966
2 971
2 998
1 967
1 991
2 999
1 992
1 999
0 999
0 825
1 938
1 854
0 824
0 790
1 853
1 820
0 789
0 776
1 801
1 733
0 775
0 729
1 732
1 690
0 728
0 638
1 689
1 620
0 637
0 361
1 583
1 414
0 360
0 221
1 288
1 156
0 220
0 12
1 22
1 10
0 11
0 0
1 0
1 1
2 0
2 13
1 2
1 9
2 14
2 71
1 23...

output:

838862656

result:

ok 1 number(s): "838862656"

Test #72:

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

input:

80
427 0
435 1
495 1
428 0
467 0
496 1
553 1
468 0
566 0
554 1
655 1
567 0
748 0
656 1
740 1
749 0
797 0
741 1
761 1
798 0
887 0
762 1
825 1
888 0
926 0
826 1
891 1
927 0
965 0
892 1
951 1
966 0
999 0
970 1
999 1
999 2
986 2
969 1
952 1
985 2
492 2
434 1
354 1
491 2
293 2
353 1
217 1
292 2
161 2
216...

output:

445383386

result:

ok 1 number(s): "445383386"

Test #73:

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

input:

91
0 4
1 18
1 44
2 76
2 32
1 17
1 10
2 31
2 29
1 9
1 6
2 21
2 13
1 4
1 5
0 3
0 1
1 3
1 2
2 12
2 3
1 1
0 0
1 0
2 1
2 0
3 0
3 4
2 2
3 5
3 19
2 22
2 28
3 20
3 61
2 77
2 78
1 45
1 69
2 79
2 92
3 62
3 122
2 93
2 99
3 123
3 135
2 100
2 165
3 136
3 191
2 166
2 178
3 192
3 195
2 188
2 179
1 184
1 196
2 193
...

output:

688776

result:

ok 1 number(s): "688776"

Test #74:

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

input:

80
52 2
66 1
32 1
16 0
41 0
67 1
75 1
42 0
114 0
122 1
135 1
140 2
187 2
136 1
159 1
115 0
125 0
160 1
166 1
126 0
196 0
186 1
195 1
195 2
196 1
197 1
197 0
199 0
198 1
199 1
199 2
198 2
199 3
196 3
197 2
196 2
195 3
194 3
189 2
194 2
185 1
167 1
188 2
193 3
133 3
139 2
131 2
132 3
20 3
80 2
130 2
1...

output:

3019

result:

ok 1 number(s): "3019"

Test #75:

score: 0
Accepted
time: 3ms
memory: 3892kb

input:

142
3 368
2 351
2 420
3 369
3 459
2 421
2 446
3 460
3 469
2 447
2 465
1 447
1 487
2 468
2 466
3 470
3 512
2 469
2 515
3 513
3 616
2 516
2 564
3 617
3 625
2 565
2 591
3 626
3 635
2 592
2 607
3 636
3 717
2 658
2 635
1 656
1 693
2 717
2 659
3 718
3 742
2 731
2 718
1 694
1 739
2 735
2 732
3 743
3 749
2 ...

output:

128369

result:

ok 1 number(s): "128369"

Test #76:

score: 0
Accepted
time: 2ms
memory: 3816kb

input:

134
552 1
527 0
702 0
633 1
679 1
703 0
714 0
680 1
700 1
699 2
716 2
722 1
701 1
715 0
734 0
736 1
737 1
735 0
739 0
738 1
743 1
740 0
749 0
744 1
749 1
749 3
746 3
748 2
746 2
745 3
744 3
745 2
741 2
735 1
723 1
720 2
740 2
743 3
737 3
719 2
717 2
736 3
680 3
698 2
663 2
679 3
631 3
662 2
605 2
63...

output:

334697

result:

ok 1 number(s): "334697"

Test #77:

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

input:

20
0 0
10 0
10 10
9 10
9 9
8 9
8 10
7 10
7 7
6 7
6 10
5 10
5 5
4 5
4 10
3 10
3 3
2 3
2 10
0 10

output:

199

result:

ok 1 number(s): "199"

Test #78:

score: 0
Accepted
time: 5ms
memory: 4212kb

input:

200
0 0
100 0
100 100
99 100
99 99
98 99
98 100
97 100
97 97
96 97
96 100
95 100
95 95
94 95
94 100
93 100
93 93
92 93
92 100
91 100
91 91
90 91
90 100
89 100
89 89
88 89
88 100
87 100
87 87
86 87
86 100
85 100
85 85
84 85
84 100
83 100
83 83
82 83
82 100
81 100
81 81
80 81
80 100
79 100
79 79
78 79...

output:

263924743

result:

ok 1 number(s): "263924743"

Test #79:

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

input:

26
0 0
5 3
6 2
20 11
20 12
25 15
27 14
40 23
40 24
45 27
50 26
60 30
59 36
55 33
50 30
48 32
35 22
35 21
30 18
26 20
15 10
15 9
10 6
8 7
-3 2
0 -1

output:

4349

result:

ok 1 number(s): "4349"

Test #80:

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

input:

8
0 0
20 -10
40 0
40 5
60 0
60 -5
80 0
40 20

output:

39

result:

ok 1 number(s): "39"

Test #81:

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

input:

10
0 0
20 -10
40 0
45 0
40 5
60 0
65 0
60 -5
80 0
40 20

output:

61

result:

ok 1 number(s): "61"

Test #82:

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

input:

4
0 0
50 -20
100 0
50 20

output:

11

result:

ok 1 number(s): "11"

Test #83:

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

input:

8
0 0
0 10
-10 0
50 -20
110 0
100 10
100 0
50 -10

output:

27

result:

ok 1 number(s): "27"