11037 - Point of View in Flatland

Darko · Post by **Darko** » Wed May 31, 2006 5:24 am

Can someone please check this I/O, I don't know if I have it right so far:

-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

[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)

Quantris · Post by **Quantris** » Wed May 31, 2006 7:55 pm

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.

Darko · Post by **Darko** » Thu Jun 01, 2006 1:17 am

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))

Quantris · Post by **Quantris** » Thu Jun 01, 2006 1:54 am

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

Darko · Post by **Darko** » Thu Jun 01, 2006 2:08 am

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

Quantris · Post by **Quantris** » Thu Jun 01, 2006 4:20 am

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

little joey · Post by **little joey** » Thu Jun 01, 2006 2:27 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.

Darko · Post by **Darko** » Thu Jun 01, 2006 4:47 pm

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)

Quantris · Post by **Quantris** » Thu Jun 01, 2006 4:51 pm

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

Darko · Post by **Darko** » Thu Jun 01, 2006 11:35 pm

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.

Quantris · Post by **Quantris** » Fri Jun 02, 2006 1:23 am

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.

luishhh · Post by **luishhh** » Mon Oct 02, 2006 12:13 am

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

Code: Select all

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

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.

little joey · Post by **little joey** » Mon Oct 02, 2006 12:34 am

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/.

Darko · Post by **Darko** » Mon Oct 02, 2006 1:46 am

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

luishhh · Post by **luishhh** » Mon Oct 02, 2006 5:27 pm

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