OJ Board

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)

I get the same absolute numbers, but where you have -1.15 1.15, I have 1.15 -1.15...

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.

Thanks, now I know who you are :)
(you probably don't remember me)

I can't figure out why my program is doing it. Back to the drawing board (I am still missing a few cases, like (r1==r2 and y1==y2))

Not fair, all I have to go on is "Darko", and that doesn't ring a bell.

I'll be watching the ranklist for this problem

I was sitting between you and Andrew in Hard Wok last October. I told you you wouldn't remember me

(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

Sure, I sort of remember

I did that problem after getting back, but not on the live archive. I really should have been able to get it the first time

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 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 did it geometrically as well (around 160 lines), though I didn't use "other curves", only points, lines, and circles. I did some algebra on paper to prove a certain fact, which it turns out would be well known to a classical geometer

I felt lazy, so I submitted without considering a couple of special cases - and it worked

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.

For a pair of "planets", you can show that the isoobservation points lie on a circle (if the planets have equal radius, they lie on the perpendicular bisector of the line connecting the centers -- consider this a circle of "infinite" radius and the statement is true for this case as well).

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.

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

It is a Waterloo problem, and the testdata can be found here http://plg.uwaterloo.ca/~acm00/060527/data/.

I guess I was wrong...

It was set by Prof. Rudnicki of U of Alberta, that's why I thought it wouldn't be posted.

Darko

Thank you very much for the link little joey,
In fact I had only a silly mistake, so the algorithm proved to be completely correct, it is almost the same as in the second official solution