Problem F
Two Points and Curious MumboJumbo
Input: Standard Input
Output: Standard
Output
Given two points a and b on a two dimensional plane, a curious mind can play many curious games. One such curious game would be to draw two pairs of parallel lines through these points, the first pair being inclined at and angle of θ1 and the second pair being inclined at an angle of θ2 with ab, resulting in a parallelogram. Let the other two points on the parallelogram be c and d such that c is the one lying on left hand side when looking at b from a. So now we have the parallelogram acbd having diagonals ab and cd. Now the mathematical mind sees that it has discovered an interesting way of constructing parallelograms from a pair of points and decides to name this operation mumbo and happily defines a notation for this operation mumbo(a,b). Note that the parallelograms produces by mumbo(a,b) and mumbo(b,a) for any two points on the plane have same shape but different orientation.
To take the game a little farther, the mathematical mind divides the diagonal ab into three equal parts ae,
ef and fb.
Joining e with c and f with d
produces a strange picture that farther increases the curiosity of the
mathematical mind. To satisfy its curiosity the mind decides to apply the
operation mumbo on these 5 line segment. The result after applying mumbo(a,e), mumbo(e,f), mumbo(f,b), mumbo(e,c) and mumbo(f,d) is an even strange picture showing five smaller
parallelograms inside the initial larger parallelogram. All six of the
parallelograms have similar shape but some has different orientation and they
have same size except for the initial one which in fact contains all the other
parallelograms inside itself. Happily, the mind names this operation of
producing smaller parallelograms of same shape jumbo. The notation for this
operation is jumbo(a,d,b,c)
where a,d,b and c are the
vertices of the parallelogram in counter clockwise order.
The mind takes the game even farther by recursive mumbo jumbo many times,
resulting in a very strange picture consisting of parallelograms of same shape
but different sizes and orientations. Now, to satisfy the ultimate curiosity,
for any two points P1 and P2
on the plane, the mind wants to know the area of the smallest parallelogram not
containing any other parallelogram that contains both of these points. To keep
things simple, mind has decided that θ1 should be
the anglecab
and always be tan-1(1) and θ2 should be the angleabd and always be tan-1(½).
There will be multiple test cases, each on a seperate line. Each line will contain eight floating point numbers Xa, Ya, Xb, Yb, Xp1, Yp1, Xp2, Yp2 denoting coordinates of a,b,p1 and p2 respcetively. Here a and b are the points to start mumbo jumbo with. You can assume that p1 and p2 will be distinct and at least 10-6 units apart.
For each line of input, your program should produce a line of output consisting of a single floating point number having four digits after decimal point denoting the area of the smallest parallelogram produced by mumbo jumbo which contains both p1 and p2 but does not contain any other parallelogram that contain both of these points. If either or both of the points are outside of the parallelogram, the print -1 as output. If a point lies exactly on a vertex of a parallelogram then the point is considered to be inside the parallelogram.
0 0 81 0 9 1 9 9 0
0 81 0 27 0 27 13.5 0
0 81 0 27 0 27 13.5 0
0 81 0 0 0 300 3 0 0 81 0 3 0 3 3 |
27.0000 243.0000 243.0000 -1 3.0000 |
Problemsetter: Raiyan Kamal
Special
Thanks to: