UOJ Logo Universal Online Judge

UOJ

#135. 【UR #9】包子晚宴

统计

为了庆祝 UOJ Round #9 的成功开赛,主办方为大家准备了一桌包子晚宴。NOI出题人也被邀请参加了包子晚宴。

谁知包子晚宴吃到一半,突然主办方把面具一摘,露出他的真身 —— 奸笑熊:“还记得我吗?我就是因为你的寿司晚宴才没拿金牌的!”

NOI出题人大惊失色,原来这是鸿门宴!

奸笑熊一挥手,所有的门窗都被关闭了。奸笑熊掌心朝上,所有的包子都悬浮在了空中,再那么一指,所有的包子形成了一张大幕,朝NOI出题人飞去。

还好还好,NOI出题人玩过东方 Project,熟悉躲子弹的那一套理论。

 

我们假设晚宴所在的房间是二维的,是一个宽度为 $w$ 高度为 $h$ 的矩形,NOI出题人可以抽象为一个没有大小的点,包子可以抽象为一个圆。

我们以矩形左上角为原点,宽为 $x$ 轴(正方向向右)高为 $y$ 轴(正方向向下)建立平面直角坐标系。

假设NOI出题人的位置在 $(x, y)$,那么NOI出题人的中弹范围是一个以 $(x, y)$ 为圆心,半径为 $r$ 的圆;NOI出题人的擦弹范围是一个以 $(x, y)$ 为圆心,半径为 $R$ 的圆。保证 $R > r$。

一共 $n$ 个子弹,编号为 $1$ 到 $n$,其中第 $i$ 个子弹在 $t_{a_i}$ 时刻出现,在 $t_{b_i}$ 时刻后消失。出现时位置为 $(x_i, y_i)$,速度为 $(v_{x_i}, v_{y_i})$(表示一个单位时间内横向移动 $v_{x_i}$,纵向移动 $v_{y_i}$)。子弹将保持这一速度移动直至消失。

得分有两种途径:

  1. 不中弹得分:有 $k$ 个时间区间 $[t_{s_i}, t_{e_i}]$。如果在 $t_{s_i} \sim t_{e_i}$ 这段时间内(包括首尾)没有任何一个子弹的圆与NOI出题人的中弹范围相交(包括外切、内切、内含),则获得 $s_i$ 的分数;
  2. 擦弹得分:每个子弹有一个擦弹得分 $g_i$,如果一个子弹的圆与NOI出题人的擦弹范围在某个时刻相交(包括外切、内切、内含),则获得 $g_i$ 的分数。若对同一个子弹多次擦弹,则只记一次

一个子弹的中弹和擦弹判定只在整数时刻进行,即时刻 $t_{a_i}, t_{a_i} + 1, \dots, t_{b_i}$。

在时刻 $i$,NOI出题人可以决定他时刻 $i$ 到时刻 $i + 1$ 这段时间内向哪一个方向移动,也可以选择不动(“S”)。可以选择的方向有 $8$ 种:上(“W”)、下(“X”)、左(“A”)、右(“D”)、左上(“Q”)、左下(“Z”)、右上(“E”)、右下(“C”)(后四种方向夹角均为 $45^{\circ}$)。NOI出题人在一个单位时间内移动的距离为定值 $d$。

NOI出题人不允许出房间,即NOI出题人的位置要在矩形内。

奸笑熊说只要NOI出题人获得的分数足够高就放他一马,于是现在NOI出题人想获得尽量高的得分。

输入格式

本题为提交答案题。所有输入数据 touhou1.in~touhou10.in 见数据下载。

对于每组数据,输入文件的第一行有七个数 $w, h, x_0, y_0, d, r, R$,分别表示矩形的宽度和高度、NOI出题人在时刻 $0$ 的初始位置、一个时刻内移动的距离、中弹和擦弹判定圆的半径。

第二行有一个正整数 $n$,表示出现的总子弹数。

接下来 $n$ 行,每行有八个数 $t_{a_i}, t_{b_i}, x_i, y_i, v_{x_i}, v_{y_i}, r_i, g_i$,分别表示每个子弹的出现和消失时间、出现时的位置、移动速度、半径和擦弹得分。

接下来一行有一个非负整数 $k$,表示结算分数的时间区间的数量。

接下来 $k$ 行,每行有三个数 $t_{s_i}, t_{e_i}, s_i$,分别表示每个时间区间的开始时刻、结束时刻和不中弹得分。

最后一行有一个数 $T$,表示游戏持续的总时间。

输出格式

针对给定的 $10$ 个输入文件 touhou1.in~touhou10.in,你需要分别给出你的输出文件 touhou1.out~touhou10.out

对于每组数据,输出文件只有一行 $T$ 个字符,第 $i$ 个字符表示NOI出题人在时刻 $i − 1$ 到时刻 $i$ 的移动方向。

样例一

input

10 10 0 0 3 1 2
2
1 2 1 0 2 0 1 5
3 3 4 2 0 0 1 5
2
0 2 10
2 3 10
3

output

CDS

explanation

时刻 $0$,NOI出题人的位置在 $(0,0)$。

时刻 $1$,在位置 $(1,0)$ 出现了一个子弹,NOI出题人移动到位置 $(2.12132,2.12132)$。

此时NOI出题人与子弹距离为 $2.39945$,获得擦弹得分 $5$。

时刻 $2$,子弹移动到位置 $(3,0)$,NOI出题人移动到位置 $(5.12132,2.12132)$。此时NOI出题人与子弹距离为 $3$,仍然擦弹但不再得分,同时该子弹消失。

在时刻 $[0,2]$ 内NOI出题人未中弹,获得不中弹得分 $10$。

时刻 $3$,在位置 $(4,2)$ 出现了一个子弹,NOI出题人位置 $(5.12132,2.12132)$。此时NOI出题人与子弹距离 $1.12786$,NOI出题人中弹,同时获得擦弹得分 $5$。

在时刻 $[2,3]$ 内NOI出题人中弹,未能获得不中弹得分。

总得分为 $20$。

评分方式

对于每组测试数据,我们设置了 $9$ 个评分参数 $a_{10}, a_9, a_8, \dots, a_2$。如果你的输出不合法,则得 $0$ 分。否则,在你的方案中,若游戏得分为 $w_{user}$,你的分数将会由下表给出:

得分条件得分条件
10$w_{user} \geq a_{10}$5$w_{user} \geq a_5$
9$w_{user} \geq a_9$4$w_{user} \geq a_4$
8$w_{user} \geq a_8$3$w_{user} \geq a_3$
7$w_{user} \geq a_7$2$w_{user} \geq a_2$
6$w_{user} \geq a_6$1$w_{user} > 0$

如果同时满足多个条件,则取最高分作为你的分数。

如何测试你的输出

在终端中先切换到该试题的目录下:(windows用户请使用cmd)

cd touhou

我们提供checker这个工具来测试你的输出文件是否是可接受的。使用这个工具的方法是,在终端中运行

./checker_linux64 <case_no>

其中case_no是测试数据的编号。例如

./checker_linux64 3

将测试 touhou3.out 是否可以接受。(windows用户请使用checker_win32 3)(什么你是windows 64位?放心吧可以运行win32应用程序的。)

当然我们有对应的linux 32位版本:checker_linux32。如果linux用户发现无法运行程序,请尝试执行chmod +x checker_linux64chmod +x checker_linux32后重试。

其它操作系统请安装 node.js 然后使用 node checker.js <case_no> 运行checker。

在你调用这个程序后,checker将根据你给出的输出文件给出测试的结果。

 

为了方便你调试,我们提供的 checker 中还增加了一些功能。你在使用 checker 时可以调用选项来获得一些额外的信息。可调用的选项包括:

  1. –p:输出每个时刻角色所在的位置。
  2. –m:输出每次中弹的相关信息。
  3. –g:输出每次擦弹的相关信息(对同一个子弹多次擦弹只输出第一次)。
  4. –t:在每个时间区间结束时显示是否获得不中弹得分。
  5. –x:将调用以上四种选项所产生的信息不输出到屏幕上,而是输出到对应的 touhou*.log 文件中。

调用选项的方法如下例所示:

./checker_linux64 3 –m –g –x

将检查 touhou3.out 是否可以接受。如果 touhou3.out 可以接受,则在输出得分的同时将每次中弹和擦弹的相关信息输出到 touhou3.log 中。

以上所有信息均按时间顺序输出。

注意比赛时提交此题显示的成绩就是最终成绩。

下载

输入数据及checker下载


或者逐个上传: