自动搬运

查看原文

来自洛谷，原作者为

	Mine_King 欢迎访问个人博客：caijimk.netlify.app

搬运于2025-08-24 23:02:05，当前版本为作者最后更新于2024-09-10 16:37:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Problem

[COTS/CETS 2022] 点组 Točkice

题目大意：

平面上有 $n$ 个点，无三点共线，两个人轮流操作，每次选择两个点连一条线段，要求不与之前的线段在非顶点处相交，无法操作者输，问先手必胜还是后手必胜。

Solution

猜结论题。

首先对于凸包上的边显然不会被其他线段影响，所以可以先把这些边连起来。

然后如果你比较会手玩且比较会猜，那么你可以得到结论：无论如何操作，最终连上的边数都相同。

考虑证明这个东西。以下用 $n$ 表示凸包点数，$m$ 表示凸包内的点数。首先对于凸包，显然最终连起来的是三角剖分，边数永远都是 $n + n - 3 = 2n - 3$。

然后考虑凸包内有恰好一个点的情况，显然他会与凸包上若干个点连边，然后将凸包划分成若干个小凸包，小凸包内部是三角剖分。

不妨设连了 $k$ 个点，切出来的每个小凸包的大小分别是 $a_1 + 1, a_2 + 1, \ldots, a_k + 1$，则有 $\sum_{i = 1}^k a_i = n$。

此时边数为：

$$k + \sum\limits_{i = 1}^k (a_i + 1 + a_i + 1 - 3) = 2n $$

因此最终边数相同。

对于有更多点的情况，对于任何一种最终状态，任意找一个凸包内的点，找到与之相连的点形成的凸包，把这个凸包的方案改成任意一种三角剖分然后删去这个点，边数 $-3$，一直删点直到只剩凸包为止。因此边数就是 $2n - 3 + 3m$。

所以我们只要求出凸包然后求出 $m$ 即可得到答案。

Code

// 長い夜の終わりを信じながら
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n;
struct Point {
	int x, y;

	Point() = default;
	Point(int _x, int _y): x(_x), y(_y) {}
	Point operator-(const Point &b) const {return Point(x - b.x, y - b.y);}
	long long operator^(const Point &b) const {return (long long)x * b.y - (long long)y * b.x;}
} a[100005];
vector<Point> stk;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y);
	sort(a + 1, a + n + 1, [](const Point &x, const Point &y) {return x.x != y.x ? x.x < y.x : x.y < y.y;});
	stk.push_back(a[1]);
	for (int i = 2; i <= n; i++) {
		while (stk.size() > 1) {
			Point tmp = stk.back();
			stk.pop_back();
			if (((tmp - stk.back()) ^ (a[i] - tmp)) > 0) {stk.push_back(tmp); break;}
		}
		stk.push_back(a[i]);
	}
	for (int i = n - 1, top = stk.size(); i >= 1; i--) {
		while ((int)stk.size() > top) {
			Point tmp = stk.back();
			stk.pop_back();
			if (((tmp - stk.back()) ^ (a[i] - tmp)) > 0) {stk.push_back(tmp); break;}
		}
		stk.push_back(a[i]);
	}
	stk.pop_back();
	puts((n - stk.size()) % 2 ? "Bara" : "Alenka");
	return 0;
}