PDF《IOI 2018 中国国家集训队集中培训》

IOI

2018 中国国家集训队集中培训 第四试 时间:2017 年12 月6日08:30 ? 12:30 题目名称 我的生命已如风中 残烛 榕树之心 某位歌姬的故事 题目类型 传统型 传统型 传统型 目录 game core rmq 可执行文件名 game core rmq 输入文件名 game.

in core.in rmq.in 输出文件名 game.out core.out rmq.out 每个测试点时限 10.0 秒3.0 秒1.0 秒 内存限制

512 MB

512 MB

512 MB 测试点数目

10 5

7 每个测试点分值

10 20

14 提交源程序文件名 对于 C++ 语言 game.cpp core.cpp rmq.cpp 对于 C 语言 game.c core.c rmq.c 对于 Pascal 语言 game.pas core.pas rmq.pas 编译选项 对于 C++ 语言 -O2 -lm -std=c+ +11 -O2 -lm -O2 -lm 对于 C 语言 -O2 -lm -O2 -lm -O2 -lm 对于 Pascal 语言 -O2 -O2 -O2 IOI

2018 中国国家集训队集中培训 第四试 我的生命已如风中残烛(game) 我的生命已如风中残烛(game) 【题目描述】 九条可怜是一个贪玩的女孩子. 这天她在一堵墙钉了 n 个钉子,第i个钉子的坐标是 (xi, yi).接着她又在墙上钉上 了m根绳子,绳子的一端是点 si(sxi, syi),绳子经过点 ti(txi, tyi),同时绳子的长度是 Li. 其中 si 点是 . 粘在墙上的,而另一个端点是可以移动的.初始情况下绳子是紧绷的一条 直线段. 接着,对每一根绳子可怜都进行了一次游戏.在第 i 次游戏中,可怜会捏着第 i 根 绳子的活动端点进行顺时针移动,移动过程中每时每刻绳子都是紧绷的. 不难发现绳子每时每刻都在以某一个位置为圆心作顺时针的圆周运动.初始情况 下圆心是绳子的固定端点 s,但是在运动的过程中圆心可能会不断发生变化,如下图 所示: 图中左侧红点为钉子所在的点,右侧红点为绳子的固定端点,其他颜色的点为虚 拟点,活动端点为紫点;

绳子从紫点开始运动,在运行到蓝点时绳子绕上左侧红点的钉 子,因此活动端点更换了圆心和半径,继续作顺时针的圆周运动.接着活动端点会运行 到绿点,并且接下来活动端点会一直绕左侧钉子不停地做圆周运动. 不难发现绳子的运动是不会停止的,因此可怜在她感觉累了之后就会停下来.但 是作为一个好奇心满满的女孩子,可怜决定对每一根绳子计算一下如果绳子无限的运 行下去,那么它的圆心会切换多少次(包括初始的圆心) .不难发现这个数值一定是有 限的. 这里对游戏过程进行一定程度的假设来简化问题: 1. 活动端点在运动的过程中距离每一个钉子的欧几里得距离始终大于等于 9*10?4 . 2. 钉子的坐标两两不同但可能有 . 多.点.共.线. 3. 钉子的体积以及绳子的体积可以忽略不计.在游戏的过程中每一段绳子之间不 会互相影响. 4. 初始情况下绳子距离每一个钉子的最近欧几里得距离大于等于

9 * 10?4 . 5. 每一根绳子初始粘着的端点 . 不.会影响绳子的运动,即.绳.子.不.会.绕.回.到.端.点.上. 第2页共10 页IOI

2018 中国国家集训队集中培训 第四试 我的生命已如风中残烛(game) 【输入格式】 从文件 game.in 中读入数据. 第一行输入一个整数 T,表示数据组数. 每组数据第一行为两个整数 n, m,表示钉子数和绳子数. 接下来 n 行,每行两个整数 xi, yi 表示钉子的坐标. 接下来 m 行,每行五个整数 sxi, syi, txi, tyi, Li 表示一段绳子,含义如上所述. 【输出格式】 输出到文件 game.out 中. 对于每组数据的每组询问,输出一行一个整数表示运行的过程中圆心变化了多 少次. 不同数据组数之间 . 无.需空行隔开. 【样例