题目描述
某二维世界中有一个山地,山体可以用一个函数 f ( x ) f(x) f ( x ) 描述,其表示横坐标 x x x 的位置海拔高度为 h = f ( x ) h=f(x) h = f ( x ) 。这个世界里有 n + m n+m n + m 只羊,其中有 n n n 只山羊和 m m m 只绵羊。我们知道第 i i i 只山羊所在的横坐标是 p i p_i p i ,第 j j j 只绵羊所在的横坐标是 q j q_j q j ,但不知道它们所在的高度。不过,我们知道山羊们所在的位置海拔集中在一个较高的范围,而绵羊们所在的位置海拔集中在一个较矮的范围。你需要根据山羊和绵羊的分布情况猜测山体形态 f ( x ) f(x) f ( x ) ,使得山羊高度的方差和绵羊高度的方差都尽可能小,同时山羊高度尽可能高于绵羊高度。
形式化地,令
u ˉ = 1 n ∑ i = 1 n f ( p i ) \bar{u}=\frac{1}{n}\sum_{i=1}^n f(p_i)
u ˉ = n 1 i = 1 ∑ n f ( p i )
v ˉ = 1 m ∑ j = 1 m f ( q i ) \bar{v}=\frac{1}{m}\sum_{j=1}^m f(q_i)
v ˉ = m 1 j = 1 ∑ m f ( q i )
表示山羊、绵羊分别的平均高度,你的目标就是构造函数 f f f ,最小化代价
cost ( f ) = 1 u ˉ − v ˉ [ ∑ i = 1 n ( f ( p i ) − u ˉ ) 2 ] + [ ∑ j = 1 m ( f ( q j ) − v ˉ ) 2 ] \operatorname{cost}(f)=\frac{1}{\bar{u}-\bar{v}}\sqrt{\left[\sum_{i=1}^n (f(p_i)-\bar{u})^2\right]+\left[\sum_{j=1}^m (f(q_j)-\bar{v})^2\right]}
cost ( f ) = u ˉ − v ˉ 1 [ i = 1 ∑ n ( f ( p i ) − u ˉ ) 2 ] + [ j = 1 ∑ m ( f ( q j ) − v ˉ ) 2 ] 当然,你还需要保证 u ˉ > v ˉ + 10 − 9 \bar u > \bar v + 10^{-9} u ˉ > v ˉ + 1 0 − 9 。
方便起见,你需要使用傅里叶级数描述 f f f 。即给定 k k k ,你需要求出最优的形如 f ( x ) = ∑ i = 1 k a i cos ( i x ) + b i sin ( i x ) f(x)=\sum_{i=1}^k a_i\cos(ix)+b_i\sin(ix) f ( x ) = ∑ i = 1 k a i cos ( i x ) + b i sin ( i x ) 的函数 f f f ,并输出 a i , b i a_i,b_i a i , b i 表示答案。请你保证 10 − 9 ≤ max i = 1 k { ∣ a i ∣ , ∣ b i ∣ } ≤ 10 9 10^{-9}\le \max_{i=1}^k\{|a_i|,|b_i|\} \le 10^9 1 0 − 9 ≤ max i = 1 k { ∣ a i ∣ , ∣ b i ∣ } ≤ 1 0 9 。数据保证存在满足上述限制的最优解。
本题开启 Special Judge。给定容错度 ϵ = 10 − E \epsilon=10^{-E} ϵ = 1 0 − E 。当你给出的函数 f f f 与答案给出的函数 f ∗ f^* f ∗ 满足 cost ( f ) < max ( ϵ + cost ( f ∗ ) , ( 1 + ϵ ) cost ( f ∗ ) ) \operatorname{cost}(f)<\max(\epsilon+\operatorname{cost}(f^*),(1+\epsilon)\operatorname{cost}(f^*)) cost ( f ) < max ( ϵ + cost ( f ∗ ) , ( 1 + ϵ ) cost ( f ∗ )) 时认为你的答案正确。
输入格式
输入共三行。
第一行三个整数 n , m , k , E n,m,k,E n , m , k , E ;
第二行 n n n 个整数,第 i i i 个数为 p i p_i p i ;
第三行 m m m 个整数,第 j j j 个数为 q j q_j q j 。
输出格式
输出 k k k 行,每行两个浮点数 a i , b i a_i,b_i a i , b i 。
提示
样例 1 解释
观察到 cos ( 10838702 ) = cos ( − 10838702 ) ≈ 1 = cos ( 0 ) \cos(10838702)=\cos(-10838702)\approx 1 =\cos(0) cos ( 10838702 ) = cos ( − 10838702 ) ≈ 1 = cos ( 0 ) ,cos ( 1 ) = cos ( − 1 ) ≈ 0.5403023 \cos(1)=\cos(-1)\approx 0.5403023 cos ( 1 ) = cos ( − 1 ) ≈ 0.5403023 。即当 f ( x ) = cos ( x ) f(x)=\cos(x) f ( x ) = cos ( x ) 时,所有山羊几乎均位于同一海拔、所有绵羊均位于同一海拔、山羊所在位置均高于绵羊所在位置。此时 cost ( f ) ≈ 0 \operatorname{cost}(f) \approx 0 cost ( f ) ≈ 0 取得最优解。
值得注意的是,对于任何非零数 r r r ,函数 f ( x ) = r cos ( x ) f(x)=r\cos(x) f ( x ) = r cos ( x ) 均可视为最优解。
样例 2 解释
最优函数(之一)约为 f ( x ) = 0.6648289523 cos ( x ) − 0.1433645347 sin ( x ) + 0.6172866488 cos ( 2 x ) + 1.3647253547 sin ( 2 x ) f(x)=0.6648289523\cos(x)-0.1433645347\sin(x)+0.6172866488\cos(2x)+1.3647253547\sin(2x) f ( x ) = 0.6648289523 cos ( x ) − 0.1433645347 sin ( x ) + 0.6172866488 cos ( 2 x ) + 1.3647253547 sin ( 2 x ) ,其代价约为 3.908439063011 3.908439063011 3.908439063011 。
子任务
对于所有测试数据,保证 1 ≤ n , m ≤ 600 1 \le n,m \le 600 1 ≤ n , m ≤ 600 ,1 ≤ k ≤ min { n + m 4 , 300 } 1 \le k \le \min\{\dfrac{n+m}{4},300\} 1 ≤ k ≤ min { 4 n + m , 300 } ,0 ≤ E ≤ 9 0 \le E \le 9 0 ≤ E ≤ 9 ,0 ≤ ∣ p i ∣ , ∣ q i ∣ ≤ 10 9 0\le |p_i|,|q_i| \le 10^9 0 ≤ ∣ p i ∣ , ∣ q i ∣ ≤ 1 0 9 。
保证每个测试数据中,p i p_i p i 和 q j q_j q j 均在该测试点数据范围内以及问题有解的条件下均匀随机生成。