UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2567. 篱笆

Statistics 下载数据

Description

  小H去美国假期实践的时候遇到了一件很有趣的事情。
  话说小H的导师家的别墅后,有一块很大的草坪。本来这是一件很和美的事情。但是,草坪的后面就是一块小森林,森林里面的兔子总是跑到草坪上来吃草。当然了,吃些草倒是没什么,但是兔子们总是将他们的排泄物留在草坪上,使得主人家的两只牧羊犬吃了它们的排泄物之后总是拉肚子。于是,小H的导师需要建一道篱笆,将后院的草坪围起来。
  篱笆销售商已经将一些标准大小的篱笆放置在草坪的边界上了。这些篱笆的长度足够覆盖整个草坪的边界,但是现在的摆放却留下了很多的空隙。然而篱笆既重又难以放置,每次放下都会毁坏一些草。因此,小H及其同伴希望找出一组篱笆的放置方法,使得所有篱笆中移动最远的一段,移动的距离最少。
  抽象来说,草坪的边界可以看做一个[0,L]的区间,既有可能是一条直线,又有可能是环形的。每块篱笆的中点为C_i,可以覆盖[C_i-r,C_i+r]的范围(环形的情况类似)。我们希望移动后的篱笆覆盖的区间包含整个边界。
  由于篱笆销售商提供的篱笆数量比较多,小H及其同伴希望知道,对于询问(XY),如果只是用编号为XY的篱笆,这个最短的移动距离是多少。这样他们就可以将多余的篱笆退回,毕竟浪费可耻嘛~~

Input

  输入文件的第一行是一个整数T,为测试数据组数。
  对于每组数据,第一行有5个整数NLrQK,分别表示篱笆的数量、草坪边界的长度、和每段篱笆的半径,询问数,和边界的类型(K=1表示边界是一条直线,K=2表示边界是环形的)。保证有2rN≥L
  接下来一行有N个整数,表示C_i的值,以升序给出。
  随后有Q行,每行2个整数XY,表示一组询问。保证X≤Y且篱笆数量足够多覆盖整个边界。

Output

  对于每组数据,首先在第一行中给出一个实数,表示移动最远的篱笆需要移动的距离。随后对于每组询问,在单独的一行中给出对应的结果。所有结果精确到小数点后5位。

Sample Input

2
6 8 1 2 1
1 1 2 3 4 5
1 5
3 6
6 8 1 2 2
1 1 2 3 4 5
1 5
3 6

Sample Output

2.00000
3.00000
2.00000
1.00000
1.50000
1.50000

Hint

数据约定

  时间限制:2秒。

  0<L,r≤2^30,0≤C_i≤L。

  T=10。

数据 1 2 3 4 5 6 7 8 9 10

K 1 1 1 1 2 2 2 2 2 2

N 1100 110000 1100 12000 110 1100 120000 1100 12000 120000

Q 0 0 1000 10000 0 0 0 1000 10000 10000


 

Source

2012国家集训队Round 1 day3