/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
座標平面上に 2 つの長方形 A,B があり、一定の速度でそれぞれ平行移動します。
いずれの長方形もつねに各辺は x 軸, y 軸のいずれかに平行であり、時刻 t において、
長方形 A の左下の頂点は (U_1\times t+P_1,V_1\times t+Q_1), 右上の頂点は (U_1\times t+R_1,V_1\times t+S_1) 、
長方形 B の左下の頂点は (U_2\times t+P_2,V_2\times t+Q_2), 右上の頂点は (U_2\times t+R_2,V_2\times t+S_2) にあります。
ここで、(U_1,V_1)\neq (U_2, V_2) である事が保証されます。
時刻 t=0 から t=10^{100} までの間で長方形 A,B が重なっている、すなわち 2 つの長方形の重なりが正の面積を持つ時間の長さを求めてください。
制約
- -1000\leq P_i<R_i\leq 1000
- -1000\leq Q_i<S_i\leq 1000
- -1000\leq U_i,V_i\leq 1000
- (U_1,V_1)\neq (U_2, V_2)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
P_1 Q_1 R_1 S_1 U_1 V_1 P_2 Q_2 R_2 S_2 U_2 V_2
出力
2 つの長方形の重なりが正の面積を持つ時間の長さを出力せよ。
正しい値との相対誤差または絶対誤差が 10^{-7} 以下であれば正答とみなされる。
入力例 1
0 0 1 1 2 0 2 -1 4 2 1 0
出力例 1
3.000000000000000
時刻 t=1 から t=4 まで、かつその時に限り 2 つの長方形は重なっています。 よって重なっている時間の長さは 3 です。
入力例 2
0 0 5 5 1 1 2 2 3 3 0 -1
出力例 2
1.500000000000000
入力例 3
-5 -5 0 5 0 0 0 0 1 1 0 1
出力例 3
0.000000000000000
2 つの長方形が辺や頂点のみを共有している状態では長方形の重なりの面積は 0 であるため、2 つの長方形が重なっているとは判定されない事に注意してください。
Problem Statement
There are two rectangles A and B on a coordinate plane, each moving at a constant velocity in parallel translation.
Each side of each rectangle is parallel to x or y axis. At time t,
the bottom-left and top-right vertices of rectangle A are at (U_1\times t+P_1,V_1\times t+Q_1) and (U_1\times t+R_1,V_1\times t+S_1), respectively;
the bottom-left and top-right vertices of rectangle B are at (U_2\times t+P_2,V_2\times t+Q_2) and (U_2\times t+R_2,V_2\times t+S_2), respectively.
Here, it is guaranteed that (U_1,V_1)\neq (U_2, V_2).
Between time 0 and time t=10^{100}, find the duration that rectangles A and B overlap; in other words, the intersection of the two rectangles has a positive area.
Constraints
- -1000\leq P_i<R_i\leq 1000
- -1000\leq Q_i<S_i\leq 1000
- -1000\leq U_i,V_i\leq 1000
- (U_1,V_1)\neq (U_2, V_2)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
P_1 Q_1 R_1 S_1 U_1 V_1 P_2 Q_2 R_2 S_2 U_2 V_2
Output
Print the duration that the intersection of the two rectangles has a positive area.
Your answer is considered correct if the relative or absolute error from the correct value is at most 10^{-7}.
Sample Input 1
0 0 1 1 2 0 2 -1 4 2 1 0
Sample Output 1
3.000000000000000
The two rectangles overlap between time t=1 and t=4, but not otherwise. Thus, the duration of overlap is 3.
Sample Input 2
0 0 5 5 1 1 2 2 3 3 0 -1
Sample Output 2
1.500000000000000
Sample Input 3
-5 -5 0 5 0 0 0 0 1 1 0 1
Sample Output 3
0.000000000000000
Note that when two rectangles only share sides or vertices, the area of the intersection is 0, so they are not considered overlapping.