10809 - Great Circle

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

10809 - Great Circle

What is the condifiton for answering "undefined"?

At first I guess if there are infinitely many great circles passing through the 2 cities I should answer "undefined". But I find that for the sample input,

Code: Select all

10,0N 129,30E 10,0S 50,30W
There should be unique great circle, am I correct?
If so, why is the answer "undefined"? Thanks!
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
There are infinitely many great circles passing through the two cities in that sample case, since the two points are antipodal.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Oh thanks.....
Seems I am making mistake in my code......
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
Also, if the two cities are equal, there are many possible great circles, but the answer is unique -- the latitude of the city. (However, I'm not sure whether there are such test cases.)

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
Another interesting case:

Code: Select all

90,0S 0,0W 90,0N 0,0W

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
misof wrote:Also, if the two cities are equal, there are many possible great circles, but the answer is unique -- the latitude of the city. (However, I'm not sure whether there are such test cases.)
I don't understand. There's only one shortest route (as implied by the definition in the question). You can argue that any route that circumnavigates the globe and returns to the same place is a great circle, in which case the answer would be "undefined." But that'd be a really unfair case to test, given the statement of the problem.

The origin and destination are distinct in all the judge test cases.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
gvcormac wrote:
misof wrote:Also, if the two cities are equal, there are many possible great circles, but the answer is unique -- the latitude of the city. (However, I'm not sure whether there are such test cases.)
I don't understand. There's only one shortest route (as implied by the definition in the question). You can argue that any route that circumnavigates the globe and returns to the same place is a great circle, in which case the answer would be "undefined." But that'd be a really unfair case to test, given the statement of the problem.
My point was: Even if you DID argue that there are infinitely many great circles for these two points, according to the problem statement the answer is still DEFINED, because it is the same for all possible great circles. In other words, I understand the definition in the same way you do, I was just trying to show that this is a special case that may need to be handled on its own.
gvcormac wrote:The origin and destination are distinct in all the judge test cases.
Sadly, we didn't know this during the contest, so we had to deal with the case I mentioned

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
misof wrote:
gvcormac wrote:
misof wrote:Also, if the two cities are equal, there are many possible great circles, but the answer is unique -- the latitude of the city. (However, I'm not sure whether there are such test cases.)
I don't understand. There's only one shortest route (as implied by the definition in the question). You can argue that any route that circumnavigates the globe and returns to the same place is a great circle, in which case the answer would be "undefined." But that'd be a really unfair case to test, given the statement of the problem.
My point was: Even if you DID argue that there are infinitely many great circles for these two points, according to the problem statement the answer is still DEFINED, because it is the same for all possible great circles. In other words, I understand the definition in the same way you do, I was just trying to show that this is a special case that may need to be handled on its own.
gvcormac wrote:The origin and destination are distinct in all the judge test cases.
Sadly, we didn't know this during the contest, so we had to deal with the case I mentioned
Consider the source/destination 0N, 0W. One circle goes throught the north and south
poles; another goes around the equator. They don't have the same most northerly point.

So, while I don't think there's any real confusion about the meaning of the question,
your interpretation would give "undefined" for source == destination != n/s pole.

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
I think it depends on the definition of "arc":

If a point is a degenerate arc, then the shortest arc between two identical points clearly is a point-shaped arc. As a result, the most northerly latitude reached on this arc is the latitude of the point, which should be the answer.

On the other hand, if a point is not considered an arc, the shortest arcs between two identical points are the infinitely many great circles through the point. In general, the answer should be "undefined", except for the poles, for which it should be "90,0N", i.e. the north pole.

I'd prefer the former, which is a lot more intuitive.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
gvcormac wrote:Consider the source/destination 0N, 0W. One circle goes throught the north and south
poles; another goes around the equator. They don't have the same most northerly point.

So, while I don't think there's any real confusion about the meaning of the question,
your interpretation would give "undefined" for source == destination != n/s pole.
Why don't you trust me when I say that we want to say exactly the same thing?

Meanwhile, Christian was able to write it more clearly than I did. I agree with him that the first definition is logical -- if you want to get from A to A, you wouldn't fly around the earth to get there.

My interpretation of the problem statement:
Consider all shortest paths lying on some great circle passing through both given points. If the answer for all of them is the same, output it, otherwise output "undefined". In the case you mention, for both (in fact, for all possible) great circles the shortest path has lenght 0 and the answer is the latitude of the city, i.e. zero.

Phew. Just wanted to make it clear finally

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
misof wrote:
gvcormac wrote:Consider the source/destination 0N, 0W. One circle goes throught the north and south
poles; another goes around the equator. They don't have the same most northerly point.

So, while I don't think there's any real confusion about the meaning of the question,
your interpretation would give "undefined" for source == destination != n/s pole.
Why don't you trust me when I say that we want to say exactly the same thing?

Meanwhile, Christian was able to write it more clearly than I did. I agree with him that the first definition is logical -- if you want to get from A to A, you wouldn't fly around the earth to get there.

My interpretation of the problem statement:
Consider all shortest paths lying on some great circle passing through both given points. If the answer for all of them is the same, output it, otherwise output "undefined". In the case you mention, for both (in fact, for all possible) great circles the shortest path has lenght 0 and the answer is the latitude of the city, i.e. zero.

Phew. Just wanted to make it clear finally
Sorry, I don't understand your point at all. Are you trying to make the (obscure) point that there are an infinite number of 0-length arcs at a given point? I can't see how anybody could be confused by this.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
gvcormac wrote:Sorry, I don't understand your point at all. Are you trying to make the (obscure) point that there are an infinite number of 0-length arcs at a given point? I can't see how anybody could be confused by this.
Oh my... Sorry that I caused you that much confusion.

The only humble point I guess I was trying to make is that the reasoning "whenever there is more than one great circle passing through the given points, the answer is undefined" is false.

My first post was about showing an example when there are many great circles but a unique and well-defined answer. (Christian then provided another such example.) My second post was basically suggesting that had there been such input cases as I mention, your program would probably need a special branch to solve them correctly.

There are no obscure points in my posts (and maybe it was looking for them that caused your confusion?). I like the problem, I find the problem statement perfectly correct, my only intent was to point out a case where it is easy to make a mistake. I'm sorry if my post didn't help.

Let's put this discussion behind us... and I hope next time we will discuss some real issue

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
Did you guys use some formula for mid-point or did ternary (or binary) search? I did ternary search.

I had to to minimize (a*t^2+b*t+c) / (d*t^2+e*t+c). My assumption (which got AC) was that there is at most one extreme for t in (0;1) and I converged it up to 1e-8. 't' is the run-length over over direct line segment. The above form arises from normalized 'z' coordinate which is 'sin(lat)'. Is there O(1) algorithm to solve that? 0.002 sec is fine for ternary search, but anyway
To be the best you must become the best!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Destination Goa, your method _is_ O(1), because for any input it takes roughly the same amount of calculations. But you mean a direct formula.