QOJ.ac

QOJ

Time Limit: N/A Memory Limit: N/A Total points: 100
Statistics

本题缺少数据。

某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”,同学们纷纷离开寝室,离开教室,离开实验室,到操场参加3000米长跑运动。一时间操场上熙熙攘攘,摩肩接踵,盛况空前。

为了督促同学们长跑,体育组制作了“阳光长跑卡”,并要求同学们通过刷卡来证明自己跑过的距离。为了防止同学抄近路,体育组又在跑到上设置了很多个刷卡点,要求同学们依次刷过。为了防止同学互相代替刷卡,体育组便安排了一个老师在现场监督。然而,老师的视野范围有限,可能无法监督到所有的刷卡点。为了解决这一问题,体育组的老师来向你寻求帮助。

简要地说,我们可以把跑道看做一个以原点为圆心、半径为 $r$ 的圆。监督的老师站在原点处,视野范围为一个给定的 $n$ 边形,且顶点顺序满足以原点为中心的极角序。现让你在跑到上放置 $m$ 个等距的刷卡点,使得尽可能多的刷卡点落在老师的视野范围内(视野范围包含多边形边界)。

输入格式

第一行有两个正整数 $n$、$m$ 和一个正实数 $r$,含义详见题目描述。

随后 $n$ 行描述这个多边形。每行两个实数 $x$ 、$y$,表示多边形上的一个顶点坐标。顶点是按照逆时针顺序给出的。

输出格式

请输出 $m$ 行,每行两个实数 $x$、$y$(用一个空格隔开),表示刷卡点的坐标。建议输出保留 $15$ 位有效数字。

评测方法

对于每个测试点,我们会先检测你输出的方案是否合法。合法的方案需满足以下两点:

  1. 每个刷卡点到原点的距离与 $r$ 的相对误差不超过 $10^{-10}$。
  2. 相邻两个刷卡点的距离与 $a$ 的相对误差不超过 $10^{-9}$。其中,$a$ 为半径为 $r$ 的圆的内接正 $m$ 边形的边长。

若你的方案合法,则直接统计你的方案中在老师视野范围内的刷卡机个数,记作 $yourans$。我们设置了 $10$ 个评分参数 $a_1 \leq a_2 \leq \cdots \leq a_{10}$,若 $yourans\geq a_i$,你的得分为 $i$。(同时满足多个取最高分)

特别地,若你的方案不合法,则我们会选取你输出文件中第一行描述的点,记作 $P$。随后在 $OP$ 射线上选取一个点 $Q$,使得 $|OQ|=r$。接下来以原点为中心对 $Q$ 进行旋转,从而生成一个合法的方案当作你的方案按上述规则进行评分,但你的得分会因此减少 $2$ 分(扣至 $0$ 为止,不会出现负分)。

样例输入

7 6 1.3
1 0
2 1
2 2
1 1.0000000001
-1 1
-1.5 -1
0 -0.5

样例输出

1.27136243102707 0.27136243102707
0.40067445661139 1.23671337820012
-0.87068797441569 0.96535094717305
-1.27136243102707 -0.27136243102708
-0.40067445661138 -1.23671337820012
0.87068797441569 -0.96535094717304

数据规模和约定

对于 $60\%$ 的数据,$n, m \leq 5\,000$;

对于 $100\%$ 的数据,$3\leq n, m\leq 100\,000$,$1 \leq r \leq 3$。

Upload a .zip file containing :


or upload files one by one: