#2367. 分形
分形
分形
题目描述
第二题:分形(程序文件名:fractal.exe)100分,运行时限:1s 分形是分数维的,介于2 维与3 维之间。完整的分形图往往具 有有界的面积和无限的周长。为了探寻分形的奥秘,King 执着地进 行着与众不同的研究。首先他研究简单分形:平面上有一个半径为 R0(R0=105)的圆,圆心处于坐标原点,它与若干个半径为R1的圆外 切,每个半径为R1的圆与若干个半径为R2的圆外切,……,每个半 径为Ri的圆与若干个半径为Ri+1的圆外切。任意两圆不相交、不重 叠、不内含、不内切。半径为Ri的圆只可能与半径为Ri-1或Ri+1的圆 外切,i>0 时恰与1 个半径为Ri-1的圆外切。作为基础,他先研究有限 层的简单分形,即只由半径为R0~Rn的圆构成的n+1 层分形。图1 是一个5 层简单分型。由于只 有有限层,所以此图的边界为有限长。 King 在边界上找出了与分形图的性质有关的若干个点对(Pi,Qi),他想知道沿着圆的边界 从Pi到Qi,最短的光滑路径的长度是多少(如图1 中的加粗曲线)。 光滑路径是指:路径在两圆公切点拐弯时切 线方向保持不变。图2 中左边两段(加粗)路径是 P Q 图1 图2
2005-7-8 光滑的,而右边的(加粗)路径不光滑。 【输入格式】(input.txt) 从文件input.txt 中读入数据,文件第一行为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<Ri<Ri-1-1。接下来的 m 行表示各个圆,每行有4 个数Xi,Yi,Si和Fi,(Xi,Yi)是圆i 的圆心位置,圆i 的半径是RSi,与圆i 相切的尺寸更大的圆的编号是Fi,Xi和Yi可能是实数,并且X1=Y1=S1=F1=0。再接下来的t 行表示 各个特殊点对,每行有4 个数PiW,PiA,QiW和QiA,用于描述一个特殊点对(Pi,Qi)的位置:PiW表示 点Pi处于PiW这个圆上,并且以此圆圆心为原点的幅角为PiA(0<=PiA<2π)。QiW表示点Qi处于QiW 这个圆上,并且以此圆圆心为原点的幅角为QiA(0<=QiA<2π)。输入数据保证PiW≠QiW,任意特殊点 不会同时处于两个圆上(即切点处无特殊点)并且一个圆最多与10 个圆相切。 【输出格式】(output.txt) 输出文件output.txt 中包含t 行,其中第i 行是一个整数 Li,表示从点Pi到点Qi的最短光滑路径的长度/π 后精确到整数 的结果。 【输入输出样例】 input.txt output.txt 1 3 3 175000 50000 150000 0 0 0 0 200000 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 x y 1 3 2 P1 Q1 P2 Q2 x y 1 3 2 P3 Q3
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
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