logo AlgoBeat OnlineJudge
登录 注册

#10062. [Sleeping Cup #1] C. Moving like a spider

内存限制:512 MiB 时间限制:1000 ms 输入文件:spider.in 输出文件:spider.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

如图,这是一张蜘蛛网。这张蜘蛛网有以下要素:

  • 中心点 ,即图中左侧用黄字标出的那个点;
  • 由中心点 引出的 条射线(图中只画了 条),分别记为直线 ,……,
  • 足够多个以中心点 为圆心的同心圆(图中只画了 个,并且每个圆只画了一段圆弧),分别记为圆 ,……。
  • 圆与射线形成的若干个交点(除了中心点 ),其中圆 和射线 的交点将被记为 。例如,图中右上角的那个交点将被记为

现有 只蜘蛛在这个蜘蛛网上运动,它们的初始位置已知(保证都不是中心点 ,因此都可以用坐标表示)。

每只蜘蛛都可以进行若干次运动(次数由你决定,也可以是 次)。一般来说,每次运动都有 个方向可选。当起点为 时:

方向 图中体现 终点 花费体力 特例
沿射线运动,远离中心点 (1)
沿射线运动,靠近中心点 (2)
沿圆顺时针运动 (3)
沿圆逆时针运动 (4)

其中,最后一列 个格子的内容从上到下分别是:

  1. 当起点是中心点 时(实际上,当起点是中心点 时,只能向上运动),终点可以是 中的任何一个,具体是哪一个由你决定。
  2. 时,终点将是中心点
  3. 时,终点将是
  4. 时,终点将是

现在,这 只蜘蛛需要会合。请你帮它们选择一个合适的会合地点(要么是中心点 ,要么是某个圆与射线形成的交点),并合理规划每只蜘蛛的运动路线,使得这 只蜘蛛运动所花费的体力之和最小,并给出这个最小体力和。

输入格式

第一行四个正整数

接下来 行,第 行两个整数 ,表示第 只蜘蛛的初始位置

输出格式

一行一个整数,表示答案。

样例

样例输入 #1

3 7 9 8
0 2
6 4
0 5

样例输出 #1

32

样例输入 #2

2 2 3 5
0 1
1 1

样例输出 #2

3

样例输入 #3

7 11 63599913 20656382
9 9
1 11
6 4
0 4
1 15
2 11
6 20

样例输出 #3

2393965956

数据范围与提示

样例 1 解释

一种最优的方案是,将会合点选在

  • 号蜘蛛沿 的路径运动(即向上运动 次),花费的体力为
  • 号蜘蛛沿 的路径运动(即先向右运动 次,再向上运动 次),花费的体力为
  • 号蜘蛛待在原地即可,花费的体力为

故答案为

样例 2 解释

一种最优的方案是,将会合点选在

  • 号蜘蛛沿 的路径运动(即先向下运动 次,再向上运动 次),花费的体力为
  • 号蜘蛛待在原地即可,花费的体力为

故答案为