luogu#P10876. [COTS/CETS 2022] 点组 Točkice

    ID: 516 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>博弈论2022O2优化CEOI(中欧)COCI(克罗地亚)

[COTS/CETS 2022] 点组 Točkice

题目背景

译自 Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) D2T3。1s,0.5G\texttt{1s,0.5G}

题目描述

鱼和光在玩游戏。

焰在二维平面上画了 NN 个点 (xi,yi)(x_i,y_i),其中任意三点不共线。

从鱼开始,两人轮流玩游戏:

  • 选择两个点 (xi,yi),(xj,yj)(x_i,y_i),(x_j,y_j)iji\neq j)。若连接这两点的线段不与之前的线段相交,则在两点间连一条线段。
  • 不能操作的玩家负。

需要注意的是:线段可以在顶点处相交(即可以共用一个顶点)。

鱼和光都绝顶聪明,焰想知道鹿死谁手。

输入格式

第一行,一个整数 NN

接下来 NN 行,每行两个整数 xi,yix_i,y_i

输出格式

如果先手(鱼)胜,输出 Alenka;否则输出 Bara

4
0 0
0 10
10 0
10 10
Alenka
5
2 1
1 3
6 4
3 5
5 2
Alenka
4
4 2
2 4
2 2
1 1
Bara

提示

对于 100%100\% 的数据,保证:

  • 1N1051\le N\le 10^5
  • 1xi,yi1061\le x_i,y_i\le 10^6
  • 任意三点不共线。
子任务编号 分值 NN\le
11 1313 77
22 1717 300300
33 2121 10001\, 000
44 4949 10510^5