11037 - Point of View in Flatland

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

11037 - Point of View in Flatland

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:

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
[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
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

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 :o

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

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
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

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
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

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 :o

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

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)
Last edited by Darko on Thu Jun 01, 2006 8:16 pm, edited 1 time in total.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

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
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

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
New poster
Posts: 26
Joined: Mon Oct 25, 2004 8:11 pm
Location: Spain

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.
"From lost to the river" --> Spanish quote

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

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
New poster
Posts: 26
Joined: Mon Oct 25, 2004 8:11 pm
Location: Spain

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
"From lost to the river" --> Spanish quote

Post Reply

Return to “Volume 110 (11000-11099)”