/home/toolbox/public_html/solutions/106/10674/a.c
1
2 /* @JUDGE_ID: 47124AK 10674 C */
3 /* coded:
4 For: lsuacm-practice
5 By: Matt Eastman (after class discussion)
6 */
7
8
9 #include <math.h>
10 #include <stdio.h>
11 #include <stdlib.h>
12
13 /* swap between opposite and adjacent given one and the hypotenuse */
14 #define swap(a, b) sqrt((b) * (b) - (a) * (a))
15
16 /* find the hypotenuse given the other two sides */
17 #define gethyp(a, b) sqrt((a) * (a) + (b) * (b))
18
19 /* find the distance between two points */
20 #define dist(p1, p2) sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y))
21
22 typedef struct
23 {
24 double x;
25 double y;
26 } coord;
27
28 typedef struct
29 {
30 coord p1;
31 coord p2;
32 double length;
33 int next;
34 } answer;
35
36 coord c1, c2;
37 double r1, r2;
38
39 int firstAnswer;
40 int answerCount;
41 answer answers[10];
42
43 void getInput()
44 {
45 r1 = 0; /* just in case scanf fails */
46
47 scanf("%lf %lf %lf %lf %lf %lf", &c1.x, &c1.y, &r1, &c2.x, &c2.y, &r2);
48 }
49
50 void addAnswer(coord p1, coord p2, double length)
51 {
52 int prev = -1;
53 int curr = firstAnswer;
54
55 answers[answerCount].p1 = p1;
56 answers[answerCount].p2 = p2;
57 answers[answerCount].length = length;
58
59 while (curr >= 0 && p1.x > answers[curr].p1.x)
60 prev = curr, curr = answers[curr].next;
61 if (curr >= 0 && p1.x == answers[curr].p1.x)
62 while (curr >= 0 && p1.y > answers[curr].p1.y)
63 prev = curr, curr = answers[curr].next;
64
65 answers[answerCount].next = curr;
66 if (prev >= 0)
67 answers[prev].next = answerCount;
68 else
69 firstAnswer = answerCount;
70
71 answerCount++;
72 }
73
74 void findExternalTangents()
75 {
76 double a, d, dy, dx;
77 double mysin, mycos;
78 double length;
79 coord p1, p2;
80
81 a = r1 - r2;
82 d = dist(c1, c2);
83 dy = c2.y - c1.y;
84 dx = c2.x - c1.x;
85 length = sqrt(d * d - a * a);
86
87 mysin = (a * dx - swap(a, d) * dy) / d / gethyp(dy, dx);
88 mycos = (a * dy + swap(a, d) * dx) / d / gethyp(dy, dx);
89
90 p1.x = c1.x + r1 * mysin;
91 p1.y = c1.y + r1 * mycos;
92 p2.x = c2.x + r2 * mysin;
93 p2.y = c2.y + r2 * mycos;
94
95 addAnswer(p1, p2, length);
96
97 mysin = (swap(a, d) * dx - a * dy) / d / gethyp(dy, dx);
98 mycos = (a * dx + swap(a, d) * dy) / d / gethyp(dy, dx);
99
100 p1.x = c1.x + r1 * mycos;
101 p1.y = c1.y - r1 * mysin;
102 p2.x = c2.x + r2 * mycos;
103 p2.y = c2.y - r2 * mysin;
104
105 addAnswer(p1, p2, length);
106 }
107
108 void findOneTangent()
109 {
110 coord p1;
111
112 p1.x = c1.x + (c2.x - c1.x) * r1 / dist(c1, c2);
113 p1.y = c1.y + (c2.y - c1.y) * r1 / dist(c1, c2);
114
115 addAnswer(p1, p1, 0);
116 }
117
118 void findInternalTangents()
119 {
120 coord p1, p2;
121 double length;
122 double d, t, dy, dx;
123 double mysin, mycos;
124
125 d = dist(c1, c2);
126 t = d / (1 + r2 / r1);
127 dx = c2.x - c1.x;
128 dy = c2.y - c1.y;
129 length = sqrt(t * t - r1 * r1) + sqrt((d - t) * (d - t) - r2 * r2);
130
131 mysin = (swap(r1, t) * dx + r1 * dy) / t / gethyp(dy, dx);
132 mycos = (r1 * dx - swap(r1, t) * dy) / t / gethyp(dy, dx);
133
134 p1.x = c1.x + r1 * mycos;
135 p1.y = c1.y + r1 * mysin;
136 p2.x = c2.x - r2 * mycos;
137 p2.y = c2.y - r2 * mysin;
138
139 addAnswer(p1, p2, length);
140
141 mysin = (swap(r1,t) * dx - r1 * dy) / t / gethyp(dy, dx);
142 mycos = (r1 * dx + swap(r1,t) * dy) / t / gethyp(dy, dx);
143
144 p1.x = c1.x + r1 * mycos;
145 p1.y = c1.y - r1 * mysin;
146 p2.x = c2.x - r2 * mycos;
147 p2.y = c2.y + r2 * mysin;
148
149 addAnswer(p1, p2, length);
150 }
151
152 void solve()
153 {
154 double x, c, y;
155
156 /*
157 * 0 tangents (little circle inscribed by big circle)
158 * 1 tangent (little circle inscribe by big circle and touching at one point)
159 * 2 tangents (two circles intersecting at two points)
160 * 3 tangents (two circles, not inscribed, touching at one point)
161 * 4 tangents (two circles, neither inscribing each other or touching)
162 * infinite tangents (two identical circles)
163 */
164
165 x = abs(r1 - r2);
166 c = dist(c1, c2);
167
168 if (c <= x)
169 {
170 if (x == 0 && c == 0) /* there are an infinte number of tangents */
171 answerCount = -1;
172
173 /* if (c < x) there are no tangents */
174
175 else if (c == x) /* there is one tangent */
176 findOneTangent();
177 }
178 else
179 {
180 findExternalTangents();
181
182 y = r1 + r2;
183
184 /* if (c < y) there are two tangents */
185
186 if (c == y) /* there are three tangents */
187 findOneTangent();
188
189 else if (c > y) /* there are four tangents */
190 findInternalTangents();
191 }
192 }
193
194 int main()
195 {
196 int i;
197
198 getInput();
199 while (r1 != 0)
200 {
201 firstAnswer = -1;
202 answerCount = 0;
203
204 solve();
205
206 printf("%d\n", answerCount);
207 for (i = firstAnswer; i != -1; i = answers[i].next)
208 printf("%.5lf %.5lf %.5lf %.5lf %.5lf\n", answers[i].p1.x,
209 answers[i].p1.y, answers[i].p2.x, answers[i].p2.y, answers[i].length);
210
211 getInput();
212 }
213
214 return EXIT_SUCCESS;
215 }
216