All submissions for this problem are available.
You are given two circles C1 and C2 with radius R1 and R2 respectively. It is given that R1 < R2 and these two circles have exactly two intersection points say P and P'. In the two points of intersection P has larger y-coordinate and in case both P and P' have same y-coordinate than P has larger x-coordinate. Now draw a circle C3 which touches C1 externally and C2 internally and have maximum radius over all such possible circles. Draw another circle C4 which touches C1 externally, C2 internally and C3 externally. There are exactly two such circles so choose the one whose center is farther from P. Similarly, draw circles Ci's, such that Ci touches C1 externally, C2 internally and Ci-1 externally. Only one such circle is possible for i>=4. Let Oi be the center of Ci. Suppose line POi cuts cirle Ci at Ai and Bi. For each circle Ci, i>=3 , lets us define Miraculous point Mi. ith Miraculous point Mi, is a point on line segment POi such that
distance(P,Mi ) = ( 2 * distance(P,Ai) * distance(P,Bi ) )/( distance(P,Ai )+ distance(P,Bi ) )
You would be asked Q queries. Each query is of the form (i x y r). All you need to do is find a circle passing through Mi, Mi+1 and Mi+2 and find the number of points of intersection of this circle with the circle with center (x,y) and radius r. If there are exactly two points of intersection, print the coordinates in two different line in ascending order( first print the point whose x coordinate is lesser and if they are equal then print first print the point with lesser y coordinate). In all other cases print -1. If points Mi, Mi+1 and Mi+2 are collinear then print -1.
The first line of the input contains an integer T denoting the number of test cases. For each test case:
- First line contains three space separated floating numbers x, y and r denoting the coordinate of the center and radius for circle C1.
- Second line contains three space separated floating numbers x, y and r denoting the coordinate of the center and radius for circle C2.
- Third Line contains an interger Q denoting the number of queries. It would be followed by Q lines.
- Each line contains an 4 space separated numbers i, x, y, r . i is an integer. x, y and r are floating point numbers.
For each query:
- If points Mi, Mi+1 and Mi+2 are collinear then print -1.
- If there are exactly two points of intersection, print the coordinates in two different line in ascending order( first print the point whose x coordinate is lesser and if they are equal then print first print the point with lesser y coordinate).
- Otherwise print -1.
- 1 <= T <= 50
- 0 <= Q <= 1000
- 3 <= i <= 2*106
- all floating point numbers <= 108
- Your output must be correct upto three places of decimal.
Input: 1 0 0 1 2 0 2 2 3 0 1 2 3 0 5 1
Output: 0.279423 -0.980384 1.720577 -0.019616 -1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions