题解 P10876 【[COTS/CETS 2022] 点组 Točkice】

· · 题解

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;
}