#2098. 尺规作图

    ID: 2098 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTS赛事:contest1637来源:qoj.ac数据:公开样例高精度构造数学

尺规作图

尺规作图

题目描述

IOI2015 中国代表队选拔赛暨全国信息学精英赛 第一试 尺规作图 尺规作图 【问题描述】 来自软件工程系的小W 正在工程制图的考场上,而他只带了一把被岁月磨 光了刻度的直尺和一副圆规。百般无奈的他只能求助于有着惊人几何作图能力的 你。现在请你使用不带刻度的直尺和圆规帮助小W 又快又精确地完成制图。 我们来简化一下这个问题,假设小W 已经得到了坐标系及单位长度,他需 要你用尺规作出长度 𝐿0 ,即得到点 (𝐿0, 0)。 你可以使用以下三种操作:

  1. 𝑙𝑖𝑛𝑒(𝐴, 𝐵) :作过点 𝐴 与点 𝐵 的直线;
  2. 𝑐𝑖𝑟𝑐𝑙𝑒(𝑂, 𝐴, 𝐵):以 𝐴𝐵 间距离为半径,以点 𝑂 为圆心画圆;
  3. 𝑖𝑛𝑡𝑒𝑟𝑠𝑒𝑐𝑡(𝑖, 𝑗):标记第 𝑖 个图形与第 𝑗 个图形的所有交点,有多个则标记 多个。 初始时小W 为你提供了原点 𝑂(0,0),为0 号点。单位长度由1 号点 (1,0) 给 出。此外提供x 轴(0 号图形)和y 轴(1 号图形)。 所有在操作中得到的新的点和图形会接下去标号。 设当前标号为 𝑛 ,则 𝑖𝑛𝑡𝑒𝑟𝑠𝑒𝑐𝑡 操作产生的点会被标记为 𝑛+ 1。 若两图形没有交点则不会产生新的点。 若有两个交点,则 𝑥 值较小(𝑥 值相同时 𝑦 较小的)的会被标记为 𝑛+ 1,另 一个为 𝑛+ 2。 请你得到点 (𝐿0, 0),并指明其编号。你不需要得到精确值,但你与精确值的 差距以及你所使用的操作数与你的得分相关。 【输入格式】 该题为提交答案型试题,所有输入数据draw1.in~draw10.in已在试题目录下。 每一个输入数据 𝑥0 为一个python 的计算表达式。其中 ∗∗ 表示幂次运算,如 3 ∗∗ 2 表示 32,2 ∗∗ 0.5 表示 √2。 为提供较高精度,表达式中的数转为 𝑑𝑒𝑐𝑖𝑚𝑎𝑙 类型,即高精度小数。其中 𝐷𝑒𝑐𝑖𝑚𝑎𝑙(2) 就表示2。 输入保证数与符号,符号与符号之间会用一个空格间隔。 python 代码的输出为要求构造的数。 注意直接用python 计算得到的结果是近似值,而实际要求的是精确值,即 与选手获得结果进行比较的值是精确值。 另外,我们还提供了一个文件draw.pdf,用适宜阅读的方式给出了每组数据 的表达式。 【输出格式】 针对给定的10 个输入文件draw1.in~draw10.in,你需要分别提交你的输出 文件draw1.out~draw10.out。 输出文件的第一行一个整数 𝑛,表示操作数。接下来 𝑛 行,每行一条操作, 三种操作对应格式为: 第8 页 共11 页 IOI2015 中国代表队选拔赛暨全国信息学精英赛 第一试 尺规作图 line: L A B circle: C O A B intersect: I i j 参数意义如题目描述所述。 在输出文件的最后一行,有一个整数表示最终获得的点的编号。 【样例输入】 Decimal( 2 ) ** ( Decimal( 1 ) / Decimal( 2 ) ) 【样例输出】 5 C 0 0 1 I 1 2 C 0 1 3 L 1 3 I 0 3 5 【样例说明】 样例中的五个操作意义如下:
  4. 以 𝑂 点为圆心,单位长度为半径画圆,该圆为 2 号图形;
  5. 取 2 号图形(圆)与y 轴交点,交点编号 2(0, −1), 3(0,1);
  6. 以 𝑂 点为圆心,以 1 号点与 3 号点的距离为半径画圆,该圆为 3 号图形;
  7. 连结点 (1,0), (0,1),生成直线为 4 号图形。
  8. 取 3 号图形(圆)与x 轴交点,交点编号 4(−√2, 0),5(√2, 0)。 因此 5 号节点就是最终需要得到的节点。 【评分方法】 针对给定的10 个输入文件draw1.in~draw10.in,我们分别提供评分参数文 件draw1.ans~draw10.ans。 评分参数文件共十行,每行两个数 𝑐𝑖, 𝑥𝑖,表示若最终得到的点 (𝑥, 0) 的横坐 标 𝑥 与 𝐿0 的绝对值之差不能超过 10−𝑥𝑖,且使用操作数 𝑛≤𝑐𝑖,则可得 𝑖 分。 评测将取所有满足条件的最高分,若不满足任何条件得0 分。 【如何测试你的输出】 我们提供checker 这个工具来测试你的输出文件是否是可接受的。使用这个 工具的方法是,首先进入终端,在终端中运行下面的命令进入本题的文件夹 cd draw 然后运行: ./checker <case_no> 其中case_no 是测试数据的编号。例如: 第9 页 共11 页 IOI2015 中国代表队选拔赛暨全国信息学精英赛 第一试 尺规作图 ./checker 3 将测试draw3.out 是否可以接受。 在你调用这个程序后,checker 将根据你给出的输出文件给出测试的结果, 其中包括:
  9. 非法退出:未知错误
  10. Invalid parameters for checker.:传递给checker 的参数不合法。
  11. Input/Output file does not exist.:输入/输出文件不存在。
  12. Output invalid:输出文件有误,此时可能包含具体错误信息。
  13. Correct! Your answer is n. Your score is s.:输出可接受,使用的操作数为 n,该测试点得分为 𝑠 。 【更多功能】 checker 还可以检查任意输入输出文件的测试结果,方法是在终端中运行: cd draw ./checker <input_file> <output_file> <ans_file> 其中input_file,output_file 和ans_file 分别是输入输出和评分参考文件的名 称。 例如 ./checker draw3.in draw3.out draw3.ans 将测试draw3.out 是否可以接受。 使用“-w”可以输出生成的每个点的坐标。输出中每行格式为 id x y 分别表示点的编号,x 坐标,y 坐标。具体用法是: ./checker -w <input_file> <output_file> <ans_file> 或者 ./checker -w <case_no> 例如 ./checker -w draw3.in draw3.out draw3.ans 使用“-i”可以同时输出选手输出,方便调试。具体用法是: ./checker -i <input_file> <output_file> <ans_file> 或者 ./checker -i <case_no> 例如 ./checker -i draw3.in draw3.out draw3.ans 使用“-e prec”可以指定checker 运算时的精度(有效位数)。不使用该选项 时默认 𝑝𝑟𝑒𝑐 为 200。具体用法是: ./checker -e <input_file> <output_file> <ans_file> 或者 ./checker -e <case_no> 例如 ./checker -e 50 draw3.in draw3.out draw3.ans “-e prec”,“-w”与“-i”选项可同时添加,顺序不限,如 ./checker -w -i -e 50 draw3.in draw3.out draw3.ans 第10 页 共11 页 IOI2015 中国代表队选拔赛暨全国信息学精英赛 第一试 尺规作图 【提示】 我们可以利用python 得到表达式的近似值,具体的,在终端中运行python 之后,输入: from math import * from decimal import * getcontext().prec = 100 然后将输入文件中的表达式(python 代码)复制到该终端窗口中并回车,即 可得到表达式的近似值(上述代码中的100 可替换为你想得到的精度)。 【特别提示】 如果选手使用自己生成输入文件进行调试,有可能因规模过大造成checker 出错。若发生这类情况,请尝试较小规模的数据。 请妥善保存输入文件draw*.in、你的输出文件draw*.out 和评分参数文件 draw*.ans,及时备份,以免误删。 第11 页 共11 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

Decimal( 2 ) ** Decimal( 32 )
64 100
56 100
48 100
44 100
40 100
37 100
34 100
31 100
29 100
28 100

样例 2

Decimal( 31 ) ** Decimal( 21 )
1000 50
400 50
200 50
160 50
125 50
100 50
80 50
60 50
50 50
44 50