Code: Select all

```
-5 0 1 10 -10 2 0 5 1
-5 0 1.2 10 -10 2 0 5 1
-5 0 1 10 -10 2 0 5 1.2
-5 0 1 10 -10 2.825 0 5 1
0 0 0 0 0 0 0 0 0
```

Code: Select all

```
-1.15 1.15
-2.26 0.64
-0.64 2.26
0.00 0.00
```

**Moderator:** Board moderators

Can someone please check this I/O, I don't know if I have it right so far:
[Edit] Now that I look at it, it seems wrong - are those two middle ones transposed somehow? (btw, I get other two points for those two cases to be (7.26,-21.36) and (21.36,-7.26), respectively - I don't think they can be on that side)

Code: Select all

```
-5 0 1 10 -10 2 0 5 1
-5 0 1.2 10 -10 2 0 5 1
-5 0 1 10 -10 2 0 5 1.2
-5 0 1 10 -10 2.825 0 5 1
0 0 0 0 0 0 0 0 0
```

Code: Select all

```
-1.15 1.15
-2.26 0.64
-0.64 2.26
0.00 0.00
```

So it looks like you have an extra negative sign for both coordinates?

Incidentally I output -0.00 on the last case there

My 2nd points for the cases (which should not be output because they give a smaller angular diameter) are

-14.48 14.48

-7.26 21.36

-21.36 7.26

-8.59 8.59

So I think you do have a negative sign issue.

(I was the guy that couldn't figure out that if you have certain amount of black and white paint in some buckets and you know what the amount of black is, then the rest is white - maybe that rings the bell)

Btw, I found out recently that this problem was available on LA, have you tried it yet?

http://acmicpc-live-archive.uva.es/nuev ... php?p=3340

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

Sorry for interrupting your conversation and getting back on topic...

I also print -0.00 for the last case above, so I think we can safely assume that such cases will not appear in the judge data. (We'll have to wait for Waterloo to put their data online to be sure.)

I liked this problem very much (especially the illustration!). As I see it, there are two ways two solve it: geometrically, by monkeying around with geometrical objects (points, lines, circles and other curves), and analytically, by monkeying around with equations. At first sight I thought the second approach would be easier, but I didn't succeed to work it all out. So I solved it geometrically (almost 200 lines of code). Is there anyone who did it the other way? I would be interested in their derivations, so if you can spare me a PM (not on the forum, of course), I would be grateful.

I also print -0.00 for the last case above, so I think we can safely assume that such cases will not appear in the judge data. (We'll have to wait for Waterloo to put their data online to be sure.)

I liked this problem very much (especially the illustration!). As I see it, there are two ways two solve it: geometrically, by monkeying around with geometrical objects (points, lines, circles and other curves), and analytically, by monkeying around with equations. At first sight I thought the second approach would be easier, but I didn't succeed to work it all out. So I solved it geometrically (almost 200 lines of code). Is there anyone who did it the other way? I would be interested in their derivations, so if you can spare me a PM (not on the forum, of course), I would be grateful.

I doubt that data will be posted - it was not set by Waterloo.

I started geometrically and ended up doing it analytically. Well, that got ugly and it didn't work, I have to sit down and go through my equations again. It comes down to intersections of parabolas (in special cases these are lines)

[EDIT] I just realized that it's an ellipse, not a parabola, nm... (one focus goes to the infinity if r1->r2)

I started geometrically and ended up doing it analytically. Well, that got ugly and it didn't work, I have to sit down and go through my equations again. It comes down to intersections of parabolas (in special cases these are lines)

[EDIT] I just realized that it's an ellipse, not a parabola, nm... (one focus goes to the infinity if r1->r2)

Last edited by Darko on Thu Jun 01, 2006 8:16 pm, edited 1 time in total.

It is 350 lines (100 is UVa-Java stuff)

Well, now I am not sure what "analytically" means - maybe I confused the phrase "analytical geometry" with something.

I wouldn't mind a hint as to why circles are enough.

You can prove it is a circle algebraically (obviously, you have to have the idea that it might be a circle, then just check it), or if you know what an Apollonian circle is then you can use a proof for that (found out later). I guess the hint would be to look up "apollonian circle" and look for proofs that it actually is a circle.

Hi! I'm getting WA in this problem, I tried Darko's input in the first post of this thread and got
is it correct?

My approach to the problem is quite simple. The goal is to reach a point such that the quotient between the distance to the center of a circle and its radius is equal for the three circles; so I just use a convex function which will be 0 in that point and a rudimentary, and possibly error-leading, algorithm to get to that point.

Code: Select all

```
2.32 -2.32
3.04 -1.91
1.91 -3.04
1.73 -1.73
```

My approach to the problem is quite simple. The goal is to reach a point such that the quotient between the distance to the center of a circle and its radius is equal for the three circles; so I just use a convex function which will be 0 in that point and a rudimentary, and possibly error-leading, algorithm to get to that point.

"From lost to the river" --> Spanish quote

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

It is a Waterloo problem, and the testdata can be found here http://plg.uwaterloo.ca/~acm00/060527/data/.Darko wrote:I doubt that data will be posted - it was not set by Waterloo.