# FRC 軟體組培訓試題 - 三維空間中的函數
###### 難度：極高
> [name=陳楷勛]

## Problem
考慮一個在三維空間中的立方體區域 $V$ 與表面 $S$，$V$ 的兩個最遠頂點分別為 $O(0,0,0)$ 和 $P(1000,1000,1000)$，即 $V$ 為在第一卦限且邊長 $1000$ 的正立方體；$S$ 可以用一個函數 $z=f(x,y)=p(a(x-x_0)^n+b(y-y_0)^m)^r+k$ 的圖形來表示，其中 $a,b,p,k,n,m,r,x_0,y_0$ 是常數。

$V$ 中初始有兩點 $A_0(x_1,y_1,z_1), B_0(x_2,y_2,z_2)$，經過 $N$ 筆移動操作之後會到達最終位置 $A_N,B_N$。對 $A_{i-1},B_{i-1}$ 而言，每筆移動操作分別為一向量 $\vec{u_i}=(u_{xi},u_{yi},u_{zi}),\vec{v_i}=(v_{xi},v_{yi},v_{zi})$，且該向量的方向代表初始移動方向；長度代表總移動距離。若 $A_{i-1},B_{i-1}$ 在移動過程中接觸到了 $V$ 的表面 $\partial V$，則其會反彈。同一筆操作可能發生多次反彈。

定義 $S$ 的「特徵點」$C$ 如下：

* 若 $S$ 的最低點（$z$ 座標最小點）存在，則定義該點為 $C$。
* 否則，若 $S$ 的最高點（$z$ 座標最大點）存在，則定義該點為 $C$。

你的目標是求出以下數值：

* $\triangle A_NB_NC$ 的面積 $s$
* $A_N$ 到 $S$ 的最短距離 $d_1$
* $B_N$ 到 $S$ 的最短距離 $d_2$

## Input
輸入的第一行為七個小數與兩個整數 $a,b,p,k,r,x_0,y_0$ 與 $n,m$，代表函數 $f$ 的參數。輸入的第二行為六個小數 $x_1,y_1,z_1,x_2,y_2,z_2$，代表 $A_0,B_0$ 的座標。輸入的第三行為一個正整數 $N$，緊接著有 $N$ 行，當中的第 $i$ 行有六個小數 $u_{xi},u_{yi},u_{zi},v_{xi},v_{yi},v_{zi}$，分別代表對 $A_{i-1},B_{i-1}$ 的移動操作，且 $1 \le i \le N$。數字之間以空白隔開。

## Output
輸出的第一行為三角形面積 $s$，第二行有兩個數字 $d_1,d_2$，數字間以空白隔開，並四捨五入至小數點後兩位。

## Constraints
* $0 \le k,x_0,y_0 \le 1000$
* $-10 \le p \le 10$，$p \ne 0$
* $0 < a,b,r,n,m \le 10$
* $n,m$ 為偶數
* $C$ 保證存在且唯一
* $A_0,B_0,C$ 必在 $V$ 內
* $f(x,y)$ 保證對所有 $(x,y)\in\mathbb{R}^2$ 皆有定義
* 對 $V$ 所在的 $xy$ 平面區域內的所有 $(x,y)$，$-10^9 \le f(x,y) \le 10^9$
* $\partial V$ 也算在 $V$ 內
* $V$ 必包含 $S$
* $S$ 可能存在於 $V$ 外
* $1 \le N \le 10^5$
* $-10^9 \le u_{xi},u_{yi},u_{zi},v_{xi},v_{yi},v_{zi} \le 10^9$，對於所有 $1 \le i \le N$

## Samples
#### Input 1

1.0 1.0 1.0 200.0 0.5 500.0 500.0 2 2
100.0 200.0 300.0 800.0 800.0 600.0
1
-100.0 -100.0 0.0 300.0 0.0 0.0

#### Output 1

153133.93
382.06 70.71

$A_0(100,200,300), B_0(800,800,600)$。在移動過程中，$A_0$ 不會與 $\partial V$ 接觸，故 $A_1=A_0+\vec{u_1}=(0,100,300)$；$B_0$ 會先移動 $200$ 單位與 $\partial V$ 接觸於 $(1000,800,600)$，再往相反方向移動 $100$ 單位 (垂直入射與出射) 到達 $B_1(900,800,600)$。

$f(x,y)=\sqrt{(x-500)^2+(y-500)^2}+200$，故 $S$ 是一個開口向上的圓錐，且錐點位於 $(500,500,200)$，恰為圖形最低點。因此 $C(500,500,200)$。

$\triangle A_1B_1C$ 的面積 $s$ 即約等於 $153133.93$。且 $A_1$ 與 $S$ 最接近的點約發生在 $(211,269,570)$，距離 $d_1 \approx 382.06$；$B_1$ 與 $S$ 最接近的點發生在 $(860,770,650)$，距離 $d_2 = 50\sqrt{2} \approx 70.71$。

## Solution
等待有心人士提供解答...