10674 - Tangents

[alex[LSD]]

First, Shahriar's problems aren't boring at all.
But I need help on this one. Please tell me if I m wrong:
1) When the centers are located in the same point there are only two possible answers : "-1" and "0"
2) Otherwise there are 5 different cases: 0 -> 1 -> 2 -> 3 -> 4. The number of tangents depends on the distance between the centers.

I WOULD ALSO APPRECIATE SOME TESTDATA!!!
[pascal]
{$N+}
Program tangents;

Const eps = 0.000000001;

Type Vect = Record
X, Y : extended;
End;

Var x1,x2,y1,y2,r1,r2,L,C,l1,c1 : extended;
V,PV : Vect;
Inversed : Boolean;
P1,P2 : Vect;
Ans : array [1..5,1..5] of extended;
i,j,k,NAns : longint;

Procedure Z(e1,e2,e3,e4,e5 : extended);
Begin
Inc(NAns);
Ans[Nans,1]:=e1; Ans[Nans,2]:=e2;
Ans[Nans,3]:=e3; Ans[Nans,4]:=e4; Ans[Nans,5]:=e5;
End;

Function Dist(var v1,v2 : vect) : extended;
Begin
Dist := sqrt((v1.x-v2.x)*(v1.x-v2.x)+(v1.y-v2.y)*(v1.y-v2.y));
End;

Function D(v1, v2 : extended) : extended;
Begin
D:=abs(v1-v2);
End;

Procedure Do_Outer;
Begin
C:=(R2-R1)*r2/L;
V.X:=(x1-x2)/L; V.Y:=(Y1-Y2)/L;
PV.X:=V.Y; PV.Y:=-V.X;

P2.X:=X2+V.X*C+PV.X*sqrt(r2*r2-c*c);
P2.y:=y2+V.y*C+PV.y*sqrt(r2*r2-c*c);
P1.X:=X1+V.X*(r1/r2)*C+PV.X*sqrt(r2*r2-c*c)*(r1/r2);
P1.y:=y1+V.y*C*(r1/r2)+PV.y*sqrt(r2*r2-c*c)*(r1/r2);

IF Inversed then
Z(P2.x, P2.Y, P1.X, P1.Y, Dist(P1,P2))
Else Z(P1.x, P1.Y, P2.X, P2.Y, Dist(P1,P2));

P2.X:=X2+V.X*C-PV.X*sqrt(r2*r2-c*c);
P2.y:=y2+V.y*C-PV.y*sqrt(r2*r2-c*c);
P1.X:=X1+V.X*(r1/r2)*C-PV.X*sqrt(r2*r2-c*c)*(r1/r2);
P1.y:=y1+V.y*C*(r1/r2)-PV.y*sqrt(r2*r2-c*c)*(r1/r2);

IF Inversed then
Z(P2.x, P2.Y, P1.X, P1.Y, Dist(P1,P2))
Else Z(P1.x, P1.Y, P2.X, P2.Y, Dist(P1,P2));

End;

Procedure Do_Inner;
Begin
l1:=L*r1/(r1+r2);
c1:=r1*r1/l1;
V.x:=(X2-x1)/L; V.y:=(y2-y1)/L;
PV.X:=V.Y; PV.Y:=-V.X;

P1.X:=x1+V.X*c1+Pv.X*sqrt(r1*r1-c1*c1);
P1.Y:=y1+V.y*c1+Pv.y*sqrt(r1*r1-c1*c1);
P2.X:=x2-V.X*c1*(r2/r1)-Pv.X*sqrt(r1*r1-c1*c1)*(r2/r1);
P2.Y:=Y2-V.Y*c1*(r2/r1)-Pv.Y*sqrt(r1*r1-c1*c1)*(r2/r1);

IF Inversed then
Z(P2.x, P2.Y, P1.X, P1.Y, Dist(P1,P2))
Else Z(P1.x, P1.Y, P2.X, P2.Y, Dist(P1,P2));

P1.X:=x1+V.X*c1-Pv.X*sqrt(r1*r1-c1*c1);
P1.Y:=y1+V.y*c1-Pv.y*sqrt(r1*r1-c1*c1);
P2.X:=x2-V.X*c1*(r2/r1)+Pv.X*sqrt(r1*r1-c1*c1)*(r2/r1);
P2.Y:=Y2-V.Y*c1*(r2/r1)+Pv.Y*sqrt(r1*r1-c1*c1)*(r2/r1);

IF Inversed then
Z(P2.x, P2.Y, P1.X, P1.Y, Dist(P1,P2))
Else Z(P1.x, P1.Y, P2.X, P2.Y, Dist(P1,P2));
End;

Begin
NAns:=0;
While true do Begin
For i:=1 to NAns do
For j:=1 to NAns-1 do
If ((Ans[j,1]-Ans[j+1,1]>Eps) OR ((D(Ans[j,1],Ans[j+1,1])<Eps) AND (Ans[j,2]>Ans[j+1,2]))) then
For k:=1 to 5 do Begin
l:=Ans[j,k]; Ans[j,k]:=Ans[j+1,k]; Ans[j+1,k]:=l;
End;

For i:=1 to NAns do Begin
For j:=1 to 5 do Begin
Write(Ans[i,j]:0:5);
write(' ');
End;
Writeln;
End;


NAns:=0;
Read(x1, y1, r1, x2, y2, r2);

If (D(x1,0.0)+D(x2,0.0)+D(y1,0.0)+D(y2,0.0)+D(r1,0.0)+D(r2,0.0) < eps )
Then Halt(0);

Inversed := False;
If R1>R2 then Begin
Inversed := TRUE;
L:=r1; r1:=r2; r2:=l; L:=x1; x1:=x2; x2:=l; L:=y1; y1:=y2; y2:=l;
End;

L:=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

If (L<Eps) then Begin
If D(r1,r2)<eps then Begin writeln('-1'); Continue; End
Else Begin Writeln('0'); Continue; End;
End;

{I}
If (R2-L-R1) > Eps Then Begin Writeln('0'); Continue; End;
{II}
If (R1+L-R2<Eps) then Begin
Writeln('1');
V.x:=(x1-x2)*(R2-R1)/L; V.y:=(y1-y2)*(R2-R1)/L;
Z(x1+V.x, y1+V.Y, x1+V.x, y1+V.Y, 0.0);
Continue;
End;
{III}
If (R1+R2-L>Eps) Then Begin
Writeln('2');
Do_Outer;
Continue;
End;
{IV}
If (R1+R2-L>-Eps) then Begin
Writeln('3');
V.x:=(x2-x1)*r1/(r1+r2); V.y:=(y2-y1)*r1/(r1+r2);
z(x1+V.x, y1+V.Y, x1+V.x, y1+V.Y, 0.0 );
Do_Outer;
Continue;
End;
{V}
If (L-R1-R2>Eps) Then Begin
Writeln('4');
Do_Outer;
Do_Inner;
Continue;
End;
End;
End.

[/pascal]

[Andrey Mokhov]

Hi!

Your approach seems to be same as mine, even the names of the functions.

But I think you use floating-point numbers too frequently. For example most of the comparisons can be done in integers only and you need floating-points only for calculating the final result.

Hope this helps. If you need test output - give me some input.

Good luck!
Andrey.

[alex[LSD]]

Thanks to all who helped, or tried to help!
Special thanks to Shahriar Manzoor.
Personally I think that geometrical problems should be in floating points all the way through. Because if they are not supposed to be solved in integers, why give integer input? Anyways it's still my humble opinion.
But my mistake wasnt about this, I had a really DUMB one in case {II}. Can you see it?

[Pawel Olchawa]

Please help ! My idea:

Let's say we we have two circles : (x1, y1, r1) and (x2, y2, r2), and have to find one of the tangents. Let's say that r1+r2 < dist( (x1,y1), (x2,y2) )

We start with two different circles : (0,r1, r1) and (a, r2, r2), where is such that dist( (0,r1), (a,r2) ) = dist( (x1,y1), (x2,y2) ). (we can easily get 'a' from pitagoras theorem for triangle (|r1-r2|, a, dist((x1,y1),(x2,y2)).

In such situtation tangent's points are (0,0) and (a,0).
We move, and rotate everything to make circles (0,r1,r1) and (a,r2,r2) become (x1,y1,r1), (x2,y2,r2). And then the previous tangent's points are those which we wanted to find.

Algorithm:

1. First I do the translation : [dx,dy] = [x1, y1-r1]

I have divided rotation into 2 rotations (in each the center of rotation is (x1,y1):
- rotate (a +dx, r2 +dy, r2) to ( ??, r1 +dy, r2 )
- rotate (??, r1+dy, r2) to (x2, y2, r2)

I dont use any tan/sin/cos functions because we know the sinus' and cosinus' values for these rotations.

rotation1: (d = dist( (x1,y1), (x2,y2) )
sin = (r1-r2) / d
cos = a / d

rotation2 :
sin = (y2-y1)/d
cos = (x2-x1)/d


We can observe that if we pass -r1 as r1 or -r2 as r2, or any combination of these we can get all 4 diff tangents.

------------------------------------------------------------------------------
source:


[cpp]#include <cstdio>
#include <cmath>
#include <utility>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i=0; i < n; ++i)
#define X first
#define Y second
#define sqr(a) ((a)*(a))
typedef pair<double, double> MYPOINT;
typedef pair<MYPOINT, MYPOINT> TANGENT;

double dist_sqr(MYPOINT& p1, MYPOINT& p2) {
return sqr(p1.X-p2.X)+sqr(p1.Y-p2.Y);
}

void rotate(MYPOINT po, MYPOINT& p, double cosinus, double sinus) {
double tx = p.X, ty = p.Y;
p.X = po.X + (tx - po.X)*cosinus - (ty - po.Y)*sinus;
p.Y = po.Y + (tx - po.X)*sinus + (ty - po.Y)*cosinus;
}

/////////////////////////////////////////////////////////////////////

TANGENT tangent(MYPOINT& p1, MYPOINT& p2, int r1, int r2) {

double a = sqrt(dist_sqr(p1,p2) - sqr(r1-r2)), // pitagoras
d = sqrt(dist_sqr(p1,p2));

double dx = p1.X, dy = p1.Y - r1; // translation vector

// tangent points:
MYPOINT s1 = make_pair(0.0 + dx, 0.0 + dy), // (0,0)
s2 = make_pair(a + dx, 0.0 + dy); // (a,0)

rotate(p1, s1, a/d, (r1-r2)/d);
rotate(p1, s2, a/d, (r1-r2)/d);
rotate(p1, s1, (p2.X - p1.X)/d, (p2.Y - p1.Y)/d);
rotate(p1, s2, (p2.X - p1.X)/d, (p2.Y - p1.Y)/d);

return make_pair(s1,s2);
}
/////////////////////////////////////////////////////////////////////

int main(void){
int x1,x2,y1,y2,r1,r2;
while (scanf("%d %d %d %d %d %d", &x1, &y1, &r1, &x2, &y2, &r2)) {
if (!x1 && !y1 && !r1 && !x2 && !y2 && !r2) break;
if (x1==x2 && y1==y2 && r1==r2) {
puts("-1");
continue;
}
pair<MYPOINT, MYPOINT> tangents[4];
int tangents_count = 0;
///////////////////////////////////
MYPOINT p1 = make_pair(x1,y1), p2 = make_pair(x2,y2);
int d = sqr(x1-x2)+sqr(y1-y2);

if (d == sqr(r1+r2)) {
// 3 tangents
tangents_count = 3;
tangents[0] = tangent(p1, p2, r1, r2);
tangents[1] = tangent(p1, p2, -r1,-r2);

MYPOINT middle = make_pair( x1+1.0*(x2-x1)*r1/(r1+r2),
y1+1.0*(y2-y1)*r1/(r1+r2) );
tangents[2] = make_pair(middle, middle);
}
else if (d > sqr(r1+r2)) {
// 4 tangents
tangents_count = 4;
tangents[0] = tangent(p1, p2, r1, r2);
tangents[1] = tangent(p1, p2, -r1,-r2);
tangents[2] = tangent(p1, p2, -r1, r2);
tangents[3] = tangent(p1, p2, r1,-r2);
}
else if (d == sqr(r1-r2)) {
// 1 tangent
tangents_count = 1;
MYPOINT middle = make_pair( x1 + 1.0*(x2-x1)*r1/(r1+r2),
y1 + 1.0*(y2-y1)*r1/(r1+r2) );
tangents[0] = make_pair(middle, middle);
}
else if (d > sqr(r1-r2)) {
// 2 tangents
tangents_count = 2;
tangents[0] = tangent(p1, p2, r1, r2);
tangents[1] = tangent(p1, p2, -r1,-r2);
}
else {
// 0 tangents
puts("0");
continue;
}
///////////////////////////////////
for (int i=0; i < tangents_count; ++i)
for (int j=tangents_count-2; j >= 0; --j)
if (fabs(tangents[j].first.X-tangents[j+1].first.X) < 0.0000001) {
if (tangents[j].first.Y > tangents[j+1].first.Y)
swap(tangents[j], tangents[j+1]);
}
else if (tangents[j].first.X > tangents[j+1].first.X)
swap(tangents[j], tangents[j+1]);

printf("%d\n", tangents_count);
REP(i, tangents_count)
printf("%.5lf %.5lf %.5lf %.5lf %.5lf\n",
tangents.first.X, tangents.first.Y,
tangents.second.X, tangents.second.Y,
sqrt(dist_sqr(tangents.first,tangents.second)));
}
return 0;
}[/cpp]


Pawel Olchawa

[tep]

Hi,
Anyone has test data, i try everything that I could, but WA, don't know what's wrong. Btw what's the output of

INPUT

-10 30 10 10 20 10

MY FRIEND'S ACC OUTPUT
4
-14.47214 21.05573 5.52786 11.05573 22.36068
-5.52786 38.94427 14.47214 28.94427 22.36068
-4.00000 22.00000 4.00000 28.00000 10.00000
-0.00000 30.00000 0.00000 20.00000 10.00000

MY OUTPUT

4
-14.47214 21.05573 5.52786 11.05573 22.36068
-5.52786 38.94427 14.47214 28.94427 22.36068
-4.00000 22.00000 4.00000 28.00000 10.00000
0.00000 30.00000 0.00000 20.00000 10.00000

[shahriar_manzoor]

There is a special judge for this problem. So zero and minus zero both are allowed.

[Cho]

I've tried everything I can, still getting WA.
I've generated 10000 test cases: 10674.in
And this is my output: 10674.out
Could somebody please tell me which of my outputs are incorrect?
or give me some critical test cases?

[..]

Great in/out, it helps me to fix many bugs
My AC program gets the same output (except for those -0.00000)
I think the key point is the precision of sorting, I used to use 1e-6 for the theshold of sorting, but this gives me WA until I change it to 2e-5(as the problem required)

[Cho]

After setting the threhold to several different values, still keep getting WA.

[Dreamer#1]

i really feel sad for you... i'm sure your solution is correct its just that unluckily you are facing some precision error... i just got AC so let me tell you what got me AC...

i used 1e-8 as Epsilon everywhere in my solution but only in the compare function for sorting the output i used 2e-5

umm.. one more thing that at times i forget is to place the check for equality before greater/less than checks when comparing real values... i know you already know all these but just incase you missed so i'm telling...

looking forward to see you get AC...
best of luck.. (i guess here luck is what you need more than anything else)

[riad]

getting WA. Some tricky test cases would be helpful.

[brianfry713]

Random input:

Code: Select all

-61 95 3 48 18 156
95 1 12 76 -9 198
-57 64 14 91 -56 127
-94 -71 28 -53 48 44
31 -4 169 -55 62 65
33 -99 81 -57 49 3
1 -7 157 -34 -31 37
98 12 128 92 -47 40
45 -91 111 -16 -43 38
-76 38 43 46 33 39
-6 -34 48 88 9 117
98 60 103 9 76 152
-88 73 34 -22 64 115
39 -42 55 -72 -7 80
-35 17 193 49 -88 15
95 -43 89 -60 -56 17
86 -59 154 -77 1 15
-20 13 149 -52 41 170
-80 -21 3 -49 7 181
-61 23 43 65 -29 14
73 -85 5 -53 -44 49
30 92 100 73 -86 163
-61 -6 178 80 -8 121
-17 12 182 95 13 25
100 52 134 -30 -34 55
54 -61 180 -56 -64 3
79 66 193 55 38 4
81 28 187 -30 -43 175
0 40 36 -92 -16 174
-76 -17 22 13 54 18
-27 -43 82 99 2 150
30 -20 143 -98 85 13
-11 16 128 -81 86 36
92 -15 106 26 -7 45
24 18 32 -77 81 159
-62 -47 95 94 -99 139
-67 -19 195 40 -67 164
85 22 7 6 -9 54
-65 -17 129 53 59 61
5 -68 179 41 -45 16
-21 -56 177 -25 -63 43
23 -80 14 -99 61 84
-36 -5 54 93 51 16
56 86 39 4 -11 14
95 94 116 4 -16 12
-57 64 177 36 89 188
-70 -38 99 7 -87 3
-34 -23 161 -3 -81 52
-81 25 65 75 -72 152
-61 -78 109 36 26 73
-13 19 49 -67 -95 131
66 86 114 69 -8 40
-18 58 24 -60 -45 72
100 -76 189 -56 100 103
-73 -62 27 54 24 138
65 -90 53 -11 94 51
53 10 126 -23 -22 189
66 11 73 30 51 137
-36 0 44 72 44 135
-42 71 24 67 -25 26
51 -61 104 -96 -21 36
-37 -69 8 8 -42 118
-56 74 73 -12 4 81
38 18 192 -89 -61 176
-16 -3 30 -5 -87 16
-21 15 6 74 -31 199
-38 33 78 -40 91 4
-13 85 122 -77 -28 54
-39 60 24 50 71 68
82 -96 194 34 -1 26
12 28 151 79 2 125
-26 14 149 -100 75 197
35 -89 9 -57 85 9
-95 -54 135 -15 46 132
55 -23 136 21 61 168
-50 -28 55 -55 -100 3
9 -26 47 5 -76 91
-59 10 60 62 53 123
54 9 111 -44 44 16
-20 -2 117 8 69 139
85 -81 51 40 -86 160
47 23 162 -32 78 188
13 69 91 70 30 96
-90 -67 7 -53 -60 95
80 20 181 89 78 8
58 12 3 50 -48 68
43 49 127 60 67 128
51 -20 123 -48 100 16
6 60 120 69 57 120
-76 36 100 29 -26 43
-98 82 68 -6 -18 182
1 -76 139 -71 34 32
-14 -16 57 10 -14 73
-36 42 2 -99 10 2
79 -15 192 -75 -87 88
-51 -85 77 85 -40 112
23 61 153 -91 90 113
-88 -75 179 -54 36 195
-72 50 6 71 1 20
-32 -71 82 -98 -46 124
0 0 0 0 0 0

AC output:

Code: Select all

0
0
4
-70.54856 60.47345 -31.90477 -87.99089 153.41121
-56.35008 77.98491 96.89574 70.86308 153.41121
-54.88298 50.16099 71.79562 69.53960 128.15225
-43.02226 64.78921 -35.79805 -63.15926 128.15225
4
-121.41749 -65.31834 -96.08463 56.92832 124.84390
-110.49613 -48.37528 -27.07751 12.44687 103.23759
-68.90141 -83.41212 -13.55936 28.49524 124.84390
-67.06883 -63.33763 -95.32042 35.95913 103.23759
2
-126.65681 56.87143 -115.63723 85.41209 30.59412
-68.58213 132.54449 -93.30082 114.51711 30.59412
4
-47.93500 -102.24426 -54.00241 49.12016 151.48597
-47.74574 -105.41295 -59.99058 48.76248 154.66092
73.11645 -28.63189 -58.48579 46.39377 151.48597
75.84279 -30.25776 -55.41323 51.54601 154.66092
0
0
2
-60.36851 -56.09332 -52.07210 -31.04997 26.38181
-13.70883 3.20336 -36.09852 -10.75020 26.38181
4
-76.35240 -4.99856 45.68038 -5.99869 122.03688
-72.83266 80.88319 48.87271 71.89406 122.03688
-48.45149 4.98365 21.01414 62.94506 90.47099
-45.84216 68.65134 18.64754 5.19995 90.47099
2
-50.00458 -14.82719 -19.26117 55.73372 76.96753
-20.26926 -79.82999 53.21868 -102.71061 76.96753
2
137.61538 -35.07692 67.46154 -64.30769 76.00000
168.24960 135.32591 112.66932 187.16057 76.00000
0
2
34.11362 -96.78251 -79.10746 -86.68365 113.67058
66.42070 5.67709 -32.11534 62.34850 113.67058
0
4
29.11693 16.83662 -47.41559 -67.42947 113.83321
40.00434 -112.97483 -49.49521 -42.63402 113.83321
47.35334 32.17177 -69.10105 -41.64135 137.87676
60.54036 -125.05811 -66.58218 -71.67402 137.87676
4
-66.89737 -40.60453 -62.10740 -0.79177 40.09988
-61.55406 -103.08853 -91.37215 -3.29434 104.15373
-42.33422 26.12536 -64.49991 -7.29143 40.09988
2.24523 70.23289 -85.15793 13.58762 104.15373
2
-49.93540 -132.96188 -86.15448 -125.53369 36.97296
120.69646 62.04596 108.52616 96.95847 36.97296
0
4
-68.57191 -19.32808 62.53473 -42.78123 133.18784
-59.27944 -19.96556 64.43982 -15.01121 123.81842
-36.51507 58.34810 72.97184 -17.49132 133.18784
-29.47772 52.24630 54.73693 -38.52205 123.81842
4
69.64948 -88.71134 -20.16495 -7.62887 121.00000
72.47514 -80.02762 -47.85635 -92.72928 121.00000
73.11951 -89.99857 -51.82878 -92.98600 124.98400
76.03820 -81.02894 -23.22562 -5.08360 124.98400
2
-69.34885 103.39326 -88.93862 -67.42899 171.94185
113.19163 147.49011 208.60236 4.44888 171.94185
2
8.63384 -169.81431 127.33536 -119.35692 128.98062
13.25210 155.77338 130.47475 101.96954 128.98062
0
2
-20.37566 110.87019 -79.40792 -9.83686 134.36890
107.09117 -81.81224 -27.08944 -88.92293 134.36890
0
0
2
-33.69054 175.69929 -137.33072 95.22126 131.21738
166.99753 -138.05248 50.47897 -198.39670 131.21738
0
4
-89.10701 0.66936 2.27608 68.45675 113.78049
-82.80279 3.92181 18.56592 36.88216 106.59268
-61.68453 -33.70531 24.71266 40.33202 113.78049
-57.11265 -28.28132 -2.45328 63.23017 106.59268
2
-89.99980 9.48833 -16.24354 98.01524 115.22587
-42.49593 -123.52252 70.65380 -145.29729 115.22587
4
-112.97344 -17.24381 -110.99759 85.25056 102.51341
-104.54614 28.43899 -85.76853 80.59646 55.43465
-43.81053 102.47859 -91.28995 73.86558 55.43465
-0.65712 119.67513 -100.78701 97.69774 102.51341
2
-128.53265 66.69592 -114.05606 100.25823 36.55133
-61.69592 133.53265 -95.25823 119.05606 36.55133
2
-9.62352 -45.14401 -17.14206 -19.79698 26.43861
0.52125 38.55034 -12.83532 15.73363 26.43861
0
2
-115.06160 -125.80017 16.36251 -214.29709 158.44242
-57.16917 47.87709 101.06826 39.82017 158.44242
2
-96.94380 -211.68723 14.81649 -229.05490 113.10172
57.00546 131.49135 144.29177 59.56708 113.10172
4
78.53846 24.69231 55.84615 -29.76923 59.00000
82.09386 15.63177 28.41877 40.12635 59.00000
86.47980 28.84180 17.41561 43.77958 70.66116
90.73792 17.99047 50.26392 -39.93065 70.66116
2
-73.56253 111.71551 48.95105 119.86547 122.78436
48.64842 -78.03308 106.74073 30.13940 122.78436
0
0
4
9.17851 -82.22853 -16.07104 74.37116 158.62219
16.62644 -92.46506 -137.24134 -13.79038 172.81493
27.19204 -66.64235 -124.15223 -19.14590 158.62219
36.25174 -75.48431 -19.48957 88.09413 172.81493
4
-43.31859 48.50176 90.83153 66.85237 135.39941
-29.99410 48.66497 91.22047 35.09927 121.97131
-1.91213 -46.88099 103.10011 38.59082 135.39941
7.30592 -37.25829 80.16862 60.55801 121.97131
4
17.00208 85.59682 17.99925 -10.85527 96.45724
18.34047 96.13707 -9.51880 -7.36105 107.18209
77.25103 53.29842 -3.62858 0.73903 96.45724
85.28835 60.24748 14.51377 -20.24449 107.18209
4
-20.09555 79.54268 -7.90644 -17.49558 97.80082
-10.87697 46.60731 14.95279 -11.09731 63.22183
68.28603 -18.88208 6.76351 -4.32254 63.22183
102.36541 -21.76593 4.76194 -27.97579 97.80082
2
-122.17323 228.56442 -33.22355 263.79159 95.67131
-30.87594 -111.06151 63.74759 -96.94104 95.67131
0
0
2
-137.37178 -7.36081 -56.82325 -147.67451 161.78999
-76.91329 89.87140 84.55660 79.69928 161.78999
2
-119.29466 14.10175 -3.04138 87.68282 137.58270
34.93402 -129.74615 100.24939 -8.65568 137.58270
2
-33.01438 63.72611 -120.50782 24.57388 95.85406
34.28587 31.84704 59.41732 -60.65382 95.85406
2
-1.45978 -5.89765 45.32990 -40.24479 58.04309
139.18233 -1.40907 94.67801 -38.66985 58.04309
4
-37.04653 43.39761 -2.86041 -1.19284 56.18719
-34.13735 75.76474 -108.41204 8.29423 100.34441
-14.59527 34.24273 -70.21419 26.27181 56.18719
5.95825 59.41508 11.87474 -40.75475 100.34441
2
-77.48448 -140.96352 -152.72435 64.59660 218.89724
185.80007 92.40234 -9.24123 191.77482 218.89724
2
-99.62700 -57.52756 -82.09357 46.85911 105.84895
-78.73168 -88.38461 24.70475 -110.85469 105.84895
4
12.65995 -81.66220 39.36496 85.97683 169.75276
15.81335 -109.74014 -58.33055 75.00477 199.06783
96.19996 -47.15654 -41.02261 52.77327 169.75276
113.78011 -69.27561 35.93935 113.94234 199.06783
2
110.17012 122.28347 62.75518 146.42520 53.20714
173.26753 -27.57288 157.40129 -78.35932 53.20714
0
2
-78.17848 12.52900 -57.41125 82.44124 72.93147
-57.41446 -38.43723 6.29654 -73.93242 72.93147
4
-58.10901 53.20956 49.54857 -44.27298 145.23429
-50.69310 48.62971 76.41753 -0.76552 136.37082
-26.38698 89.22728 83.91410 -5.25378 145.23429
-20.90703 82.44931 44.14928 -37.40342 136.37082
4
-51.98728 -75.47826 -60.35056 -15.98830 60.07495
-30.45151 3.66569 -67.80525 -43.38428 60.07495
-18.22761 -138.61146 -119.96340 -47.86550 136.32681
30.64305 40.98821 -103.04664 14.30361 136.32681
0
2
-121.27340 41.31386 -84.42665 -32.26818 82.29216
1.75555 118.64635 52.08493 53.53910 82.29216
2
-80.27195 169.24730 -197.41595 77.64336 148.70777
121.39094 -154.94493 -12.55830 -219.53286 148.70777
4
-44.69333 -11.75746 -20.30311 -91.67064 83.55238
-38.86395 -22.42266 7.19411 -76.64125 71.14071
11.09413 -15.88053 -19.45020 -80.13038 71.14071
13.98077 -4.07395 10.98974 -87.57277 83.55238
0
0
2
-134.92197 80.63722 -130.96546 -29.93107 110.63905
45.95796 -21.80805 -50.90385 -75.27569 110.63905
2
-53.25183 79.31024 9.61982 125.71235 78.14090
-48.12146 37.80093 24.15586 8.10262 78.14090
0
2
12.00000 -123.00000 79.00000 -123.00000 67.00000
113.85557 139.47396 163.31752 94.27977 67.00000
2
-50.50342 -132.97137 -132.39714 -119.31785 83.02409
113.59487 66.09869 84.56502 143.88216 83.02409
4
26.69231 -92.46154 -48.69231 88.46154 196.00000
27.04369 -93.20679 -64.95631 80.79321 196.82480
42.53826 -84.08322 -64.53826 80.08322 196.00000
42.95631 -84.79321 -49.04369 89.20679 196.82480
2
-198.41275 32.78020 -116.11469 130.85175 128.02734
12.36397 -135.84118 89.97810 -34.02248 128.02734
2
-44.92479 -115.25527 -102.43651 -52.96240 84.78207
190.96181 -19.77736 188.95283 64.98091 84.78207
4
-90.79438 -64.88928 -57.22515 -102.01214 50.04998
-85.71621 -69.82526 -53.05184 -97.71862 42.95346
-20.40781 -74.36057 -56.61412 -97.47124 42.95346
-14.69612 -70.17388 -53.07433 -102.30039 50.04998
2
-10.20648 16.89652 -32.18701 7.05496 24.08319
34.78199 13.29744 54.91833 0.08653 24.08319
2
-104.24409 49.40778 -30.75038 133.78594 111.89727
-69.22954 -49.12154 41.02945 -68.19916 111.89727
2
-56.66762 0.41639 -59.95209 42.76272 42.47352
-26.19211 85.74780 -55.55922 55.06275 42.47352
2
-136.59492 7.72757 -130.51875 80.55669 73.08215
71.84916 -74.47573 117.11995 -17.10364 73.08215
0
2
-6.21076 -130.01181 -93.75075 -99.56927 92.68225
172.03204 126.00966 113.09891 197.54207 92.68225
2
-43.68851 -2.18577 10.19674 -45.09707 68.88396
58.81429 147.62602 118.33156 112.94613 68.88396
0
0
0
2
-52.77735 132.40083 -36.53150 151.05753 24.73863
131.73331 -41.85923 149.43199 -24.57466 24.73863
4
-71.71015 -11.56087 -63.96230 101.09777 112.92475
-61.54462 29.62569 -33.36005 93.54463 69.85700
23.66585 99.92433 -44.44434 84.40009 69.85700
66.03369 102.07780 -46.04440 115.88004 112.92475
2
0.29218 -59.86418 63.29218 -62.86418 63.07139
11.70782 179.86418 74.70782 176.86418 63.07139
2
-80.69674 -63.88964 26.98040 -68.95255 107.79610
9.19980 88.35450 65.63591 -3.48756 107.79610
2
-163.85877 98.92993 -182.26906 27.31247 73.94593
-109.39253 149.03887 -36.49178 161.42757 73.94593
2
-128.53112 -25.57491 -100.82011 45.60865 76.38717
6.61814 62.88642 -69.70662 65.97385 76.38717
2
-55.27586 23.31034 -42.86207 36.34483 18.00000
-48.20000 -61.60000 -33.80000 -72.40000 18.00000
4
-37.00522 43.72903 -97.99478 8.27097 70.54786
-36.90573 43.78316 -99.90573 11.78316 70.66116
-35.19666 40.16843 -99.80334 11.83157 70.54786
-35.09427 40.21684 -98.09427 8.21684 70.66116
2
-91.72937 72.83782 -153.25096 -46.74100 134.47676
36.92162 -202.33235 -94.28592 -172.86066 134.47676
2
-92.31589 -20.02310 24.90417 54.51185 138.91004
-45.40557 -161.79650 93.13735 -151.70400 138.91004
2
-62.89328 -65.61495 -154.43752 -3.51300 110.62097
8.05061 213.26791 -102.04105 202.45930 110.62097
2
-264.74300 -46.66431 -246.54126 66.86849 114.98261
74.29231 -150.51296 122.79888 -46.26272 114.98261
4
-74.46226 44.52850 62.79246 -17.23832 150.51246
-72.93967 44.07404 74.13222 20.75321 148.90937
-70.58912 55.83176 75.70294 20.43920 150.51246
-69.10777 55.25690 61.35925 -16.52301 148.90937
2
-9.70912 -149.91208 -64.29184 -165.33047 56.71860
36.97754 -26.65929 6.30750 21.05181 56.71860

[riad]

Thanks brianfry713, just got AC
Did one stupid mistake. Initially if r1<r2 I swapped the two circles but didn't keep track of this. So outputs were printed in wrong order.

[triplemzim]

Tested all I/O found on udebug... don't know where is the problem. Still getting WA. Please help!!

Code: Select all

#include<bits/stdc++.h>

using namespace std;


#define ms(x,val) memset(x,val,sizeof(x))
#define scan(x) scanf("%d",&x)
#define print(x) printf("debug= %d\n",x)
#define ull unsigned long long
#define iii long long
#define pi acos(-1)
#define pb push_back
#define PII pair<int,int>
#define vi vecotr<int>
#define MAPL map<long long, int > 
#define MAPI map<int,int> 
#define MAPP map< pair<int,int> , int>
#define MP make_pair
#define eps (1e-9)
#define inf 999999999
#define MAXN 1000009
#define MOD 1000000007 // 10^9 + 7



struct point{
	public:
		double x,y;
		point(double x,double y){
			this->x=x;
			this->y=y;
		}
};



double _invtan(double x,double y)
{
	if(abs(x)<eps) return pi/2.0;
	return atan2(y,x);
}

double calc_dist(point a,point b)
{
	double temp=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
	return sqrt(abs(temp));
}

vector< pair< pair<double,double>,pair<double,double> > > _sort(vector< pair< pair<double,double>,pair<double,double> > > v)
{
	double prec=2e-5;
	pair< pair<double,double>,pair<double,double> > p,q;
	for(int i=0;i<v.size();i++){
		for(int j=i+1;j<v.size();j++){
			if(i==j) continue;
			p=v[i];
			q=v[j];
			if(abs(p.first.first-q.first.first)<=prec){
				if(p.first.second+eps>q.first.second){
					swap(v[i],v[j]);
				}
			}
			else if(p.first.first+eps>q.first.first){
				swap(v[i],v[j]);
			}
		}
	}
	return v;
}






int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	double a,b,c,d,r1,r2;

	while(scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&r1,&c,&d,&r2)!=EOF){
		if(!a && !b && !c && !d && !r1 && !r2) break;

		if(abs(a-c)<eps && abs(b-d) <eps && abs(r1-r2)<eps){
			cout<<-1<<endl;
			continue;
		}
		point circle_a(a,b),circle_b(c,d);

		double center_dist=calc_dist(circle_a,circle_b);
		//printf("Center distance: %.5lf\n",center_dist);

		if(center_dist<=abs(r1-r2)+eps){
			cout<<0<<endl;
			continue;
		}

		//shifting the center of first circle to zero
		circle_b.x-=a;
		circle_b.y-=b;
		c-=a;
		d-=b;

		circle_a.x=circle_a.y=0;




		vector< pair< pair<double,double>,pair<double,double> > > v;
		pair< pair<double,double>,pair<double,double> > p;


		double cline_theta=_invtan(c,d);
		double vumi=max(r1,r2)-min(r1,r2);
		double otivuj=center_dist;


		//double tan_len1=sqrt(abs(otivuj*otivuj-vumi*vumi));
		//printf("Estimated length of tangent1: %.5lf\n",tan_len1);

		double temp_theta=acos(vumi/otivuj);
		//changed here
		if(r2+eps>=r1) temp_theta=pi-temp_theta;

		temp_theta+=cline_theta;

		double tan_x1,tan_y1,tan_x2,tan_y2;

		tan_x1=r1*cos(temp_theta);
		tan_x2=r2*cos(temp_theta)+c;
		tan_y1=r1*sin(temp_theta);
		tan_y2=r2*sin(temp_theta)+d;

		tan_x1+=a;
		tan_x2+=a;
		tan_y1+=b;
		tan_y2+=b;

		//printf("debug: %.5lf %.5lf %.5lf %.5lf ",tan_x1,tan_y1,tan_x2,tan_y2);
		//printf("%lf\n",calc_dist(point(tan_x1,tan_y1),point(tan_x2,tan_y2)));
		if(center_dist+eps>=abs(r1-r2)){

			p=MP(MP(tan_x1,tan_y1),MP(tan_x2,tan_y2));
			v.pb(p);
		}

		temp_theta-=cline_theta;
		temp_theta*=-1;
		temp_theta+=cline_theta;

		tan_x1=r1*cos(temp_theta);
		tan_x2=r2*cos(temp_theta)+c;
		tan_y1=r1*sin(temp_theta);
		tan_y2=r2*sin(temp_theta)+d;

		tan_x1+=a;
		tan_x2+=a;
		tan_y1+=b;
		tan_y2+=b;

		if(center_dist+eps>=abs(r1-r2)){

			p=MP(MP(tan_x1,tan_y1),MP(tan_x2,tan_y2));
			v.pb(p);
		}
		//printf("debug: %.5lf %.5lf %.5lf %.5lf ",tan_x1,tan_y1,tan_x2,tan_y2);
		//printf("%lf\n",calc_dist(point(tan_x1,tan_y1),point(tan_x2,tan_y2)));



		//cross tangent calculation


		double temp_x2,temp_x1;
		temp_x2=(center_dist*r2)/(r1+r2);
		temp_x1=center_dist-temp_x2;

		vumi=r1;
		otivuj=temp_x1;
		temp_theta=acos(vumi/otivuj);
		temp_theta+=cline_theta;
		
		tan_x1=r1*cos(temp_theta);
		tan_y1=r1*sin(temp_theta);

		temp_theta+=pi;

		tan_x2=r2*cos(temp_theta)+c;
		tan_y2=r2*sin(temp_theta)+d;

		tan_x1+=a;
		tan_x2+=a;
		tan_y1+=b;
		tan_y2+=b;

		//printf("debug: %.5lf %.5lf %.5lf %.5lf ",tan_x1,tan_y1,tan_x2,tan_y2);
		//printf("%lf\n",calc_dist(point(tan_x1,tan_y1),point(tan_x2,tan_y2)));
		

		if(center_dist+eps>=r1+r2){
			p=MP(MP(tan_x1,tan_y1),MP(tan_x2,tan_y2));
			v.pb(p);
	//		if(abs(center_dist-r1-r2)>eps && abs(center_dist-(abs(r1-r2)))>eps){
	//			p=MP(MP(tan_y1,tan_x1),MP(tan_y2,tan_x2));
	//			v.pb(p);
	//		}
		}
		temp_theta-=pi;
		temp_theta-=cline_theta;
		temp_theta*=-1;
		temp_theta+=cline_theta;
		
		
		tan_x1=r1*cos(temp_theta);
		tan_y1=r1*sin(temp_theta);

		temp_theta=pi-temp_theta;

		tan_x2=r2*cos(temp_theta)+c;
		tan_y2=r2*sin(temp_theta)+d;

		tan_x1+=a;
		tan_x2+=a;
		tan_y1+=b;
		tan_y2+=b;
		d+=b;
		tan_y2-=d+d;
		tan_y2*=-1;

		if(center_dist+eps>r1+r2){
	//		p=MP(MP(tan_x1,tan_y1),MP(tan_x2,tan_y2));
	//		v.pb(p);
			if(center_dist+eps>=(abs(r1-r2))){
				p=MP(MP(tan_x1,tan_y1),MP(tan_x2,tan_y2));
				v.pb(p);
			}
		}
		//printf("debug: %.5lf %.5lf %.5lf %.5lf ",tan_x1,tan_y1,tan_x2,tan_y2);
		//printf("%lf\n",calc_dist(point(tan_x1,tan_y1),point(tan_x2,tan_y2)));

		if(center_dist<=eps+abs(r1-r2)){
			temp_theta=cline_theta;

			tan_x1=r1*cos(temp_theta);
			tan_y1=r1*sin(temp_theta);


			tan_x2=tan_x1;
			tan_y2=tan_y1;

			tan_x1+=a;
			tan_x2+=a;
			tan_y1+=b;
			tan_y2+=b;
			
			p=MP(MP(tan_x1,tan_y1),MP(tan_x2,tan_y2));
			v.pb(p);
		}

		cout<<v.size()<<endl;

		//sort(v.begin(),v.end());
		v=_sort(v);

		for(int i=0;i<v.size();i++){
			p=v[i];
			printf("%.5lf %.5lf %.5lf %.5lf ",p.first.first,p.first.second,p.second.first,p.second.second);
			printf("%.5lf\n",calc_dist(point(p.first.first,p.first.second),point(p.second.first,p.second.second)));
		}


	}




	return 0;
}