[HNOI2005]分形

时间限制:10s      空间限制:162MB

题目描述


输入格式

第一行为3个整数n,m和t。其中1<=n,n+1<=m<=3000,1<=t<=100000,m表示圆的个数,并且圆的编号为1~m。t为特殊点对数。 50%的数据满足m<=300,t<=1000。第二行为n个正整数R1~Rn,并且当i>=1时有1


输出格式

包含t行,其中第i行是一个整数Li,表示从点Pi到点Qi的最短光滑路径的长度/π后精确到整数的结果。


样例输入

1 3 3                          
50000                         
0 0 0 0                       
150000 0 1 1
0 150000 1 1
3 5.497787 	  2 2.356194
3 1.570796 	  2 0.0
3 0.0         2 1.570796

样例输出

175000
150000
200000

提示

没有写明提示


题目来源

鸣谢Claris制作数据