#P3. [Sleeping Cup #1] Moving like a spider
[Sleeping Cup #1] Moving like a spider
注意
本题需要使用文件读写(spider.in
/ spider.out
)。
题目描述
这里有一张图片。如果你没有看到,请点击右侧的「文件」以下载或查看。
如图,这是一张蜘蛛网。这张蜘蛛网有以下要素:
- 中心点 ,即图中左侧用黄字标出的那个点;
- 由中心点 引出的 条射线(图中只画了 条),分别记为直线 ,,,……,;
- 足够多个以中心点 为圆心的同心圆(图中只画了 个,并且每个圆只画了一段圆弧),分别记为圆 ,,,……。
- 圆与射线形成的若干个交点(除了中心点 ),其中圆 和射线 的交点将被记为 。例如,图中右上角的那个交点将被记为 。
现有 只蜘蛛在这个蜘蛛网上运动,它们的初始位置已知(保证都不是中心点 ,因此都可以用坐标表示)。
每只蜘蛛都可以进行若干次运动(次数由你决定,也可以是 次)。一般来说,每次运动都有 个方向可选。当起点为 时:
方向 | 图中体现 | 终点 | 花费体力 | 特例 |
---|---|---|---|---|
上 | 沿射线运动,远离中心点 | (1) | ||
下 | 沿射线运动,靠近中心点 | (2) | ||
左 | 沿圆顺时针运动 | (3) | ||
右 | 沿圆逆时针运动 | (4) |
其中,最后一列 个格子的内容从上到下分别是:
- 当起点是中心点 时(实际上,当起点是中心点 时,只能向上运动),终点可以是 中的任何一个,具体是哪一个由你决定。
- 当 时,终点将是中心点 。
- 当 时,终点将是 。
- 当 时,终点将是 。
现在,这 只蜘蛛需要会合。请你帮它们选择一个合适的会合地点(要么是中心点 ,要么是某个圆与射线形成的交点),并合理规划每只蜘蛛的运动路线,使得这 只蜘蛛运动所花费的体力之和最小,并给出这个最小体力和。
输入格式
第一行,四个正整数,。
接下来 行,第 行两个整数 ,表示第 只蜘蛛的初始位置 。
输出格式
一行一个整数,表示答案。
样例
3 7 9 8
0 2
6 4
0 5
32
2 2 3 5
0 1
1 1
3
7 11 63599913 20656382
9 9
1 11
6 4
0 4
1 15
2 11
6 20
2393965956
提示
样例 解释:
一种最优的方案是,将会合点选在 :
- 号蜘蛛沿 的路径运动(即向上运动 次),花费的体力为 ;
- 号蜘蛛沿 的路径运动(即先向右运动 次,再向上运动 次),花费的体力为 ;
- 号蜘蛛待在原地即可,花费的体力为 。
故答案为 。
样例 解释:
一种最优的方案是,将会合点选在 :
- 号蜘蛛沿 的路径运动(即先向下运动 次,再向上运动 次),花费的体力为 ;
- 号蜘蛛待在原地即可,花费的体力为 。
故答案为 。
对于 的数据,,,,。
相关
在下列比赛中: