QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#413898#5649. Spinach Pizzathesupermarketisgoingtome#AC ✓1ms3796kbC++172.7kb2024-05-18 11:41:342024-05-18 11:41:35

Judging History

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

  • [2024-05-18 11:41:35]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3796kb
  • [2024-05-18 11:41:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
	friend ostream& operator<<(ostream& os, P p) {
		return os << "(" << p.x << "," << p.y << ")"; }
};

typedef Point<int> P;

template<class T>
T polygonArea2(vector<Point<T>>& v) {
	T a = v.back().cross(v[0]);
	rep(i,0,sz(v)-1) a += v[i].cross(v[i+1]);
	return abs(a);
}
set<int>s;
vector<P>arr(105);
int solve(){
	vector<int>vec;
	for(int nxt: s){
		vec.push_back(nxt);
	}
	vector<P>poly = {arr[vec[0]],arr[vec[1]],arr[vec.back()]};
	int res = polygonArea2(poly);
	pair<int,int>p = {res,vec[0]};
	for(int i = 1; i+1<vec.size(); i++){
		poly = {arr[vec[i-1]],arr[vec[i]],arr[vec[i+1]]};
		res = polygonArea2(poly);
		p = min(p,{res,vec[i]});
	}
	poly = {arr[vec[0]], arr[vec[vec.size()-2]], arr[vec.back()]};

	p = min(p, {polygonArea2(poly), vec.back()});
	return p.second;
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin >> n;
	for(int i = 1; i<=n; i++){
		int x,y;
		cin >> x >> y;
		arr[i] = P{x,y};
	}
	if(n%2==0){
		cout << "Alberto" << endl;
	}
	else{
		cout << "Beatrice" << endl;
	}
	
	for(int i = 1; i<=n; i++){
		s.insert(i);
	}
	for(int i = n; i>=3; i--){
		if(i%2==0){
			int v = solve();
			cout << v << endl;
			s.erase(v);
		}
		else{
			int q;
			cin >> q;
			s.erase(q);
		}
	}
	return 0;
}

詳細信息

Test #1:

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

input:

4
0 0
6 1
5 3
1 4
4

output:

Alberto
3

result:

ok they win, their_area 7 <= our_area 23. Used strategy 0

Test #2:

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

input:

6
0 0
2 0
3 2
2 4
0 4
-1 2
3
6

output:

Alberto
1
5

result:

ok they win, their_area 8 <= our_area 16. Used strategy 0

Test #3:

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

input:

7
0 0
2 0
5 2
4 5
1 5
-1 4
-1 2
7
2
6

output:

Beatrice
5
4

result:

ok they win, their_area 19 <= our_area 28. Used strategy 0

Test #4:

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

input:

10
-96 -90
39 -96
64 -95
92 -39
95 76
10 96
-53 75
-80 55
-84 40
-93 -24
2
7
6
8

output:

Alberto
9
10
4
1

result:

ok they win, their_area 27074 <= our_area 35537. Used strategy 0

Test #5:

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

input:

8
-195 -20
-123 -172
178 -192
196 78
189 133
80 154
-147 197
-188 118
4
1
7

output:

Alberto
6
8
3

result:

ok they win, their_area 103230 <= our_area 148248. Used strategy 0

Test #6:

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

input:

100
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
11 66
12 78
13 91
14 105
15 120
16 136
17 153
18 171
19 190
20 210
21 231
22 253
23 276
24 300
25 325
26 351
27 378
28 406
29 435
30 465
31 496
32 528
33 561
34 595
35 630
36 666
37 703
38 741
39 780
40 820
41 861
42 903
43 946
44 990
45 1035
4...

output:

Alberto
2
6
10
14
18
22
26
30
34
38
42
46
50
54
58
62
66
70
74
78
82
86
90
94
98
3
11
19
27
35
43
51
59
67
75
83
91
97
13
29
45
61
77
93
25
57
89
49
33

result:

ok they win, their_area 39361 <= our_area 122339. Used strategy 0

Test #7:

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

input:

90
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
11 66
12 78
13 91
14 105
15 120
16 136
17 153
18 171
19 190
20 210
21 231
22 253
23 276
24 300
25 325
26 351
27 378
28 406
29 435
30 465
31 496
32 528
33 561
34 595
35 630
36 666
37 703
38 741
39 780
40 820
41 861
42 903
43 946
44 990
45 1035
46...

output:

Alberto
2
6
10
14
18
22
26
30
34
38
42
46
50
54
58
62
66
70
74
78
82
86
89
7
15
23
31
39
47
55
63
71
79
87
13
29
45
61
77
9
41
73
17
65

result:

ok they win, their_area 28872 <= our_area 88608. Used strategy 0

Test #8:

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

input:

99
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
11 66
12 78
13 91
14 105
15 120
16 136
17 153
18 171
19 190
20 210
21 231
22 253
23 276
24 300
25 325
26 351
27 378
28 406
29 435
30 465
31 496
32 528
33 561
34 595
35 630
36 666
37 703
38 741
39 780
40 820
41 861
42 903
43 946
44 990
45 1035
46...

output:

Beatrice
4
8
12
16
20
24
28
32
36
40
44
48
52
56
60
64
68
72
76
80
84
88
92
96
3
11
19
27
35
43
51
59
67
75
83
91
97
13
29
45
61
77
93
25
57
89
49
33

result:

ok they win, their_area 39192 <= our_area 117657. Used strategy 0

Test #9:

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

input:

97
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
11 66
12 78
13 91
14 105
15 120
16 136
17 153
18 171
19 190
20 210
21 231
22 253
23 276
24 300
25 325
26 351
27 378
28 406
29 435
30 465
31 496
32 528
33 561
34 595
35 630
36 666
37 703
38 741
39 780
40 820
41 861
42 903
43 946
44 990
45 1035
46...

output:

Beatrice
4
8
12
16
20
24
28
32
36
40
44
48
52
56
60
64
68
72
76
80
84
88
92
96
7
15
23
31
39
47
55
63
71
79
87
95
13
29
45
61
77
93
25
57
89
49
33

result:

ok they win, their_area 38904 <= our_area 108536. Used strategy 0

Test #10:

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

input:

100
-200 0
-199 -18
-198 -27
-197 -33
-194 -48
-193 -52
-189 -65
-184 -78
-170 -105
-166 -111
-161 -118
-158 -122
-150 -132
-132 -150
-122 -158
-118 -161
-111 -166
-105 -170
-93 -177
-78 -184
-65 -189
-52 -193
-48 -194
-33 -197
0 -200
18 -199
27 -198
33 -197
48 -194
52 -193
65 -189
78 -184
93 -177
1...

output:

Alberto
11
36
60
85
3
22
29
48
72
78
98
17
41
65
91
7
69
49
12
20
44
63
89
2
33
73
82
42
97
92
55
30
79
87
21
66
25
95
61
81
14
32
47
99
57
9
71
28
62

result:

ok they win, their_area 93243 <= our_area 157246. Used strategy 0

Test #11:

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

input:

99
-200 0
-199 -18
-198 -27
-197 -33
-194 -48
-193 -52
-189 -65
-184 -78
-177 -93
-166 -111
-161 -118
-158 -122
-150 -132
-132 -150
-122 -158
-118 -161
-111 -166
-105 -170
-93 -177
-78 -184
-65 -189
-52 -193
-48 -194
-33 -197
-27 -198
-18 -199
0 -200
18 -199
27 -198
33 -197
48 -194
52 -193
65 -189
7...

output:

Beatrice
16
42
66
90
5
24
31
50
56
77
98
37
60
84
12
7
95
20
62
81
89
2
35
51
74
71
78
18
68
6
47
55
13
27
70
1
80
94
8
57
87
69
97
19
4
82
64
34

result:

ok they win, their_area 88141 <= our_area 162361. Used strategy 0

Test #12:

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

input:

96
-100 0
-99 -27
-98 -38
-97 -48
-96 -55
-94 -67
-92 -78
-87 -98
-85 -105
-83 -111
-79 -122
-75 -132
-66 -150
-61 -158
-59 -161
-54 -168
-49 -174
-39 -184
-35 -187
-26 -193
-24 -194
-19 -196
-13 -198
-9 -199
0 -200
9 -199
13 -198
19 -196
24 -194
26 -193
35 -187
39 -184
49 -174
54 -168
59 -161
61 -1...

output:

Alberto
3
21
35
51
69
83
5
23
40
53
71
88
19
67
11
6
42
54
90
36
39
22
70
33
8
25
15
2
48
18
12
37
32
43
7
24
38
17
30
1
10
41
20
4
34
13
26

result:

ok they win, their_area 62606 <= our_area 62606. Used strategy 0

Test #13:

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

input:

100
-199 -18
-198 -26
-197 -33
-196 -39
-195 -44
-193 -52
-184 -78
-168 -108
-166 -111
-157 -123
-153 -128
-148 -134
-132 -150
-114 -164
-111 -166
-103 -171
-89 -179
-80 -183
-68 -188
-65 -189
-55 -192
-19 -199
19 -199
27 -198
34 -197
39 -196
51 -193
58 -191
73 -186
82 -182
98 -174
105 -170
108 -168...

output:

Alberto
2
11
20
39
56
73
88
97
32
76
18
34
65
28
5
94
44
42
85
89
37
40
59
10
3
79
72
19
92
77
50
43
86
27
54
95
17
74
22
49
84
41
29
6
81
60
75
100
87

result:

ok they win, their_area 116421 <= our_area 133839. Used strategy 0

Test #14:

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

input:

99
-199 -18
-198 -26
-197 -33
-196 -39
-193 -52
-187 -70
-184 -78
-173 -100
-168 -108
-166 -111
-157 -123
-153 -128
-148 -134
-132 -150
-122 -158
-114 -164
-103 -171
-89 -179
-80 -183
-68 -188
-65 -189
-55 -192
-33 -197
-27 -198
-19 -199
19 -199
27 -198
39 -196
51 -193
58 -191
73 -186
82 -182
98 -17...

output:

Beatrice
9
21
55
79
96
24
51
3
29
65
81
27
6
95
43
32
76
11
78
17
52
70
30
22
54
8
63
41
59
14
77
86
18
45
94
10
37
74
31
42
16
75
7
87
20
60
40
71

result:

ok they win, their_area 93598 <= our_area 156714. Used strategy 0

Test #15:

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

input:

8
-1000000 0
-707106 -707106
0 -1000000
707106 -707106
1000000 0
707106 707106
0 1000000
-707106 707106
8
6
7

output:

Alberto
2
4
1

result:

ok they win, their_area 2828424000000 <= our_area 2828424000000. Used strategy 0

Test #16:

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

input:

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

output:

Alberto
1

result:

ok they win, their_area 2000000000000 <= our_area 2000000000000. Used strategy 0

Test #17:

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

input:

4
-1000000 -1000000
1000000 -1000000
1000000 1000000
-1000000 1000000
4

output:

Alberto
1

result:

ok they win, their_area 4000000000000 <= our_area 4000000000000. Used strategy 0

Test #18:

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

input:

8
0 0
2 1
3 3
2 5
0 6
-2 5
-3 3
-2 1
8
6
7

output:

Alberto
2
4
1

result:

ok they win, their_area 24 <= our_area 24. Used strategy 0

Test #19:

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

input:

8
2 1
3 3
2 5
0 6
-2 5
-3 3
-2 1
0 0
3
7
8

output:

Alberto
1
5
2

result:

ok they win, their_area 24 <= our_area 24. Used strategy 0

Test #20:

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

input:

12
0 0
5 0
9 3
12 7
12 12
9 16
5 19
0 19
-4 16
-7 12
-7 7
-4 3
12
9
4
10
11

output:

Alberto
3
6
1
7
2

result:

ok they win, their_area 277 <= our_area 277. Used strategy 0

Test #21:

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

input:

12
5 0
9 3
12 7
12 12
9 16
5 19
0 19
-4 16
-7 12
-7 7
-4 3
0 0
5
11
4
10
12

output:

Alberto
2
8
1
7
3

result:

ok they win, their_area 277 <= our_area 277. Used strategy 0

Test #22:

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

input:

12
9 3
12 7
12 12
9 16
5 19
0 19
-4 16
-7 12
-7 7
-4 3
0 0
5 0
4
10
5
11
12

output:

Alberto
1
7
2
8
3

result:

ok they win, their_area 277 <= our_area 277. Used strategy 0

Test #23:

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

input:

16
0 0
4 1
7 3
9 6
10 10
9 14
7 17
4 19
0 20
-4 19
-7 17
-9 14
-10 10
-9 6
-7 3
-4 1
16
6
10
14
15
11
13

output:

Alberto
2
4
8
12
3
7
1

result:

ok they win, their_area 300 <= our_area 300. Used strategy 0

Test #24:

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

input:

16
4 1
7 3
9 6
10 10
9 14
7 17
4 19
0 20
-4 19
-7 17
-9 14
-10 10
-9 6
-7 3
-4 1
0 0
3
7
11
15
6
14
16

output:

Alberto
1
5
9
13
2
10
4

result:

ok they win, their_area 300 <= our_area 300. Used strategy 0

Test #25:

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

input:

16
7 3
9 6
10 10
9 14
7 17
4 19
0 20
-4 19
-7 17
-9 14
-10 10
-9 6
-7 3
-4 1
0 0
4 1
4
8
12
16
9
5
11

output:

Alberto
1
6
10
14
3
13
15

result:

ok they win, their_area 229 <= our_area 371. Used strategy 0

Test #26:

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

input:

16
9 14
7 17
4 19
0 20
-4 19
-7 17
-9 14
-10 10
-9 6
-7 3
-4 1
0 0
4 1
7 3
9 6
10 10
3
7
11
15
6
14
16

output:

Alberto
1
5
9
13
2
10
4

result:

ok they win, their_area 300 <= our_area 300. Used strategy 0

Test #27:

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

input:

8
0 0
3 2
4 6
2 9
-2 10
-5 8
-6 4
-4 1
8
6
7

output:

Alberto
2
4
1

result:

ok they win, their_area 72 <= our_area 72. Used strategy 0

Test #28:

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

input:

8
3 2
4 6
2 9
-2 10
-5 8
-6 4
-4 1
0 0
3
7
8

output:

Alberto
1
5
2

result:

ok they win, their_area 72 <= our_area 72. Used strategy 0

Test #29:

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

input:

100
-999921 -12566
-982287 -187381
-904827 -425779
-850994 -525174
-840944 -541121
-830595 -556875
-801566 -597904
-797794 -602929
-793990 -607930
-778462 -627691
-758361 -651833
-745941 -666011
-679953 -733255
-642252 -766493
-607930 -793990
-582690 -812694
-577572 -816339
-514439 -857526
-465151 -...

output:

Alberto
8
91
32
16
39
5
65
11
56
74
97
25
31
58
7
19
53
50
83
61
23
14
38
33
12
71
18
54
24
66
85
4
89
68
52
30
27
95
84
37
44
73
90
17
86
2
79
96
10

result:

ok they win, their_area 2687386613882 <= our_area 3574075078320. Used strategy 0

Test #30:

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

input:

99
-998571 -53435
-995251 -97332
-989097 -147265
-955705 -294325
-923729 -383046
-913801 -406161
-905975 -423330
-886465 -462794
-883537 -468360
-871476 -490437
-806793 -590834
-743355 -668896
-730602 -682802
-721956 -691938
-690802 -723043
-667727 -744406
-648790 -760967
-599678 -800241
-472523 -88...

output:

Beatrice
28
81
46
6
93
30
87
74
32
80
51
21
14
97
90
2
59
72
17
86
64
20
69
45
25
94
12
98
60
76
84
47
22
33
3
89
38
58
27
49
78
88
99
26
15
79
4
73

result:

ok they win, their_area 2471204190423 <= our_area 3794571420075. Used strategy 0

Test #31:

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

input:

100
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
11 66
12 78
13 91
14 105
15 120
16 136
17 153
18 171
19 190
20 210
21 231
22 253
23 276
24 300
25 325
26 351
27 378
28 406
29 435
30 465
31 496
32 528
33 561
34 595
35 630
36 666
37 703
38 741
39 780
40 820
41 861
42 903
43 946
44 990
45 1035
4...

output:

Alberto
2
6
10
14
18
22
26
30
34
38
42
46
52
56
60
64
68
72
76
80
84
88
92
96
49
3
11
19
27
35
43
57
65
73
81
89
47
5
21
37
63
79
45
9
59
41
17
33
1

result:

ok they win, their_area 49019600 <= our_area 49019600. Used strategy 0

Test #32:

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

input:

99
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
11 66
12 78
13 91
14 105
15 120
16 136
17 153
18 171
19 190
20 210
21 231
22 253
23 276
24 300
25 325
26 351
27 378
28 406
29 435
30 465
31 496
32 528
33 561
34 595
35 630
36 666
37 703
38 741
39 780
40 820
41 861
42 903
43 946
44 990
45 1035
46...

output:

Beatrice
4
8
12
16
20
24
28
32
36
40
44
48
53
57
61
65
69
73
77
81
85
89
93
97
3
11
19
27
35
43
52
60
68
76
84
92
5
21
37
54
70
86
9
41
74
17
33
1

result:

ok they win, their_area 48017248 <= our_area 49020776. Used strategy 0

Test #33:

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

input:

99
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
11 66
12 78
13 91
14 105
15 120
16 136
17 153
18 171
19 190
20 210
21 231
22 253
23 276
24 300
25 325
26 351
27 378
28 406
29 435
30 465
31 496
32 528
33 561
34 595
35 630
36 666
37 703
38 741
39 780
40 820
41 861
42 903
43 946
44 990
45 1035
46...

output:

Beatrice
4
8
12
16
20
24
28
32
36
40
44
48
54
58
62
66
70
74
78
82
86
90
94
98
3
11
19
27
35
43
57
65
73
81
89
97
5
21
37
63
79
95
9
59
91
17
83
51

result:

ok they win, their_area 48017248 <= our_area 49020776. Used strategy 0

Test #34:

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

input:

4
0 0
5 0
7 3
2 3
4

output:

Alberto
1

result:

ok they win, their_area 15 <= our_area 15. Used strategy 0

Test #35:

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

input:

98
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
11 66
12 78
13 91
14 105
15 120
16 136
17 153
18 171
19 190
20 210
21 231
22 253
23 276
24 300
25 325
26 351
27 378
28 406
29 435
30 465
31 496
32 528
33 561
34 595
35 630
36 666
37 703
38 741
39 780
40 820
41 861
42 903
43 946
44 990
45 1035
46...

output:

Alberto
2
6
10
14
18
22
26
30
34
38
42
46
51
55
59
63
67
71
75
79
83
87
91
95
3
11
19
27
35
43
52
60
68
76
84
92
5
21
37
54
70
86
9
41
74
17
33
1

result:

ok they win, their_area 48018424 <= our_area 48018424. Used strategy 0

Test #36:

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

input:

100
0 0
1 0
2 1
3 3
4 6
5 10
6 15
7 21
8 28
9 36
10 45
11 55
12 66
13 78
14 91
15 105
16 120
17 136
18 153
19 171
20 190
21 210
22 231
23 253
24 276
25 300
26 325
27 351
28 378
29 406
30 435
31 465
32 496
33 528
34 561
35 595
36 630
37 666
38 703
39 741
40 780
41 820
42 861
43 903
44 946
45 990
46 1...

output:

Alberto
1
5
9
13
17
21
25
29
33
37
41
45
49
55
59
63
67
71
75
79
83
87
91
95
99
2
10
18
26
34
42
54
62
70
78
86
94
48
8
24
40
64
80
92
4
60
36
68
84

result:

ok they win, their_area 34055 <= our_area 127645. Used strategy 0

Test #37:

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

input:

99
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
11 66
12 78
13 91
14 105
15 120
16 136
17 153
18 171
19 190
20 210
21 231
22 253
23 276
24 300
25 325
26 351
27 378
28 406
29 435
30 465
31 496
32 528
33 561
34 595
35 630
36 666
37 703
38 741
39 780
40 820
41 861
42 903
43 946
44 990
45 1035
46...

output:

Beatrice
2
6
10
14
18
22
26
30
34
38
42
46
52
56
60
64
68
72
76
80
84
88
92
96
49
7
15
23
31
39
53
61
69
77
85
93
47
13
29
55
71
87
45
25
75
41
67
33

result:

ok they win, their_area 19600 <= our_area 139650. Used strategy 0

Test #38:

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

input:

100
0 0
900000 0
900001 1
900002 3
900003 6
900004 10
900005 15
900006 21
900007 28
900008 36
900009 45
900010 55
900011 66
900012 78
900013 91
900014 105
900015 120
900016 136
900017 153
900018 171
900019 190
900020 210
900021 231
900022 253
900023 276
900024 300
900025 325
900026 351
900027 378
90...

output:

Alberto
3
5
9
13
17
21
25
29
33
37
41
45
49
55
59
63
67
71
75
79
83
87
91
95
50
4
12
20
28
36
44
58
66
74
82
90
48
6
22
38
64
80
46
10
60
42
18
34
1

result:

ok they win, their_area 1102519600 <= our_area 1102639650. Used strategy 0

Test #39:

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

input:

78
-9943 -1066
-9913 -1315
-9701 -2425
-9637 -2669
-9567 -2910
-8015 -5979
-7745 -6325
-7705 -6374
-7375 -6753
-7246 -6891
-5672 -8235
-5358 -8443
-3328 -9429
-3268 -9450
-2729 -9620
-2242 -9745
-2181 -9759
-1502 -9886
-1066 -9943
-753 -9971
125 -9999
1128 -9936
2729 -9620
3681 -9297
5358 -8443
5672...

output:

Alberto
40
76
41
74
7
71
54
4
39
75
9
64
52
14
19
45
61
37
51
48
44
68
3
53
65
69
8
62
42
25
55
43
60
77
46
5
70
63

result:

ok they win, their_area 201750791 <= our_area 422644723. Used strategy 2

Test #40:

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

input:

79
-9976 -690
-9971 -753
-9943 -1066
-9936 -1128
-9759 -2181
-9637 -2669
-9048 -4257
-8476 -5305
-8409 -5411
-7459 -6660
-6518 -7583
-5775 -8163
-4762 -8793
-3328 -9429
-3090 -9510
-941 -9955
-314 -9995
0 -10000
941 -9955
1128 -9936
1253 -9921
2120 -9772
3446 -9387
4029 -9152
4257 -9048
4762 -8793
5...

output:

Beatrice
50
2
3
48
68
55
49
72
62
25
27
77
44
51
65
9
40
33
19
35
24
60
45
54
38
75
47
64
39
71
12
17
66
11
21
37
15
8

result:

ok they win, their_area 208645485 <= our_area 417373232. Used strategy 2

Test #41:

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

input:

78
0 0
1 0
2 1
3 3
4 6
5 10
6 15
7 21
8 28
9 36
10 45
11 55
12 66
13 78
14 91
15 105
16 120
17 136
18 153
19 171
20 190
21 210
22 231
23 253
24 276
25 300
26 325
27 351
28 378
29 406
30 435
31 465
32 496
33 528
34 561
35 595
36 630
37 666
38 703
39 741
-38 741
-37 703
-36 666
-35 630
-34 595
-33 561...

output:

Alberto
1
3
5
7
9
11
13
15
17
23
28
33
44
48
50
55
57
59
61
69
71
73
29
37
62
65
8
45
49
68
32
54
10
66
74
56
6
77

result:

ok they win, their_area 1597 <= our_area 74479. Used strategy 2

Test #42:

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

input:

79
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
11 66
12 78
13 91
14 105
15 120
16 136
17 153
18 171
19 190
20 210
21 231
22 253
23 276
24 300
25 325
26 351
27 378
28 406
29 435
30 465
31 496
32 528
33 561
34 595
35 630
36 666
37 703
38 741
39 780
-39 780
-38 741
-37 703
-36 666
-35 630
-34 5...

output:

Beatrice
2
4
6
8
10
12
14
16
18
23
31
34
36
38
42
44
46
50
55
59
63
65
72
74
76
27
51
17
47
64
71
49
66
75
15
25
19
28

result:

ok they win, their_area 3910 <= our_area 76690. Used strategy 2

Test #43:

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

input:

44
-9470 -3209
-9297 -3681
-9274 -3739
-8409 -5411
-8340 -5516
-8199 -5724
-7246 -6891
-6470 -7624
-5979 -8015
-5516 -8340
-4927 -8701
-2242 -9745
-2120 -9772
1253 -9921
2729 -9620
4927 -8701
8443 -5358
9101 -4143
9798 -1997
9856 -1688
9913 -1315
9943 -1066
9998 -188
9999 -125
9971 753
9759 2181
967...

output:

Alberto
5
2
21
20
27
43
6
40
10
22
32
18
39
25
4
14
36
41
16
38
35

result:

ok they win, their_area 232642175 <= our_area 385207555. Used strategy 1

Test #44:

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

input:

45
-9995 -314
-9936 -1128
-9202 -3913
-6129 -7901
-5928 -8053
-4762 -8793
-3328 -9429
-2242 -9745
-941 -9955
-753 -9971
2729 -9620
5463 -8375
6753 -7375
6891 -7246
7203 -6936
7246 -6891
8053 -5928
8375 -5463
9745 -2242
9886 -1502
9936 -1128
9955 -941
9637 2669
9429 3328
7501 6613
5928 8053
4257 9048...

output:

Beatrice
15
21
36
45
9
5
42
27
37
17
6
30
13
19
7
11
24
18
10
28
2

result:

ok they win, their_area 200228380 <= our_area 419256849. Used strategy 1

Test #45:

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

input:

4
0 0
5 0
5 5
0 5
4

output:

Alberto
1

result:

ok they win, their_area 25 <= our_area 25. Used strategy 0

Test #46:

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

input:

44
0 0
1 0
2 1
3 3
4 6
5 10
6 15
7 21
8 28
9 36
10 45
11 55
12 66
13 78
14 91
15 105
16 120
17 136
18 153
19 171
20 190
21 210
22 231
-21 231
-20 210
-19 190
-18 171
-17 153
-16 136
-15 120
-14 105
-13 91
-12 78
-11 66
-10 55
-9 45
-8 36
-7 28
-6 21
-5 15
-4 10
-3 6
-2 3
-1 1
4
9
14
19
26
31
36
41
3...

output:

Alberto
1
6
11
16
21
28
33
38
43
7
17
22
34
10
44
27
5
32
35
2
29

result:

ok they win, their_area 2109 <= our_area 11135. Used strategy 1

Test #47:

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

input:

45
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
11 66
12 78
13 91
14 105
15 120
16 136
17 153
18 171
19 190
20 210
21 231
22 253
-22 253
-21 231
-20 210
-19 190
-18 171
-17 153
-16 136
-15 120
-14 105
-13 91
-12 78
-11 66
-10 55
-9 45
-8 36
-7 28
-6 21
-5 15
-4 10
-3 6
-2 3
-1 1
2
6
10
14
18
...

output:

Beatrice
4
8
12
16
20
25
29
33
37
41
45
7
15
26
34
42
44
28
17
5
36

result:

ok they win, their_area 1771 <= our_area 12903. Used strategy 1

Test #48:

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

input:

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

output:

Beatrice
4

result:

ok they win, their_area 8 <= our_area 30. Used strategy 0

Test #49:

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

input:

6
3 1
8 0
12 4
11 8
8 9
4 7
3
6

output:

Alberto
5
1

result:

ok they win, their_area 41 <= our_area 73. Used strategy 0

Test #50:

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

input:

5
-8 -2
9 -9
10 7
3 9
-7 6
4
3

output:

Beatrice
5

result:

ok they win, their_area 135 <= our_area 320. Used strategy 0

Test #51:

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

input:

7
-10 -10
10 -10
10 -3
9 4
6 10
-7 10
-10 9
3
4
5

output:

Beatrice
6
7

result:

ok they win, their_area 317 <= our_area 443. Used strategy 0