10809 - Great Circle

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

Moderator: Board moderators

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

10809 - Great Circle

Post by .. » Tue Feb 08, 2005 8:07 pm

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:
  • Please make discussion about the algorithm BRFORE posting source code.
    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

Post by Per » Tue Feb 08, 2005 8:13 pm

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

Post by .. » Tue Feb 08, 2005 8:20 pm

Oh thanks.....
Seems I am making mistake in my code......
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    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

Post by misof » Tue Feb 08, 2005 10:03 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.)

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Wed Feb 09, 2005 12:10 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:

Post by gvcormac » Wed Feb 09, 2005 6:19 am

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

Post by misof » Wed Feb 09, 2005 3:37 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 :D

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Wed Feb 09, 2005 3:54 pm

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 :D
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.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Wed Feb 09, 2005 4:19 pm

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

Post by misof » Wed Feb 09, 2005 10:06 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? :D

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

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Fri Feb 11, 2005 8:28 am

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? :D

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

Post by misof » Fri Feb 11, 2005 1:35 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

Post by Destination Goa » Thu Feb 17, 2005 9:04 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!

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

Post by little joey » Thu Feb 17, 2005 1:05 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.

<SPOILER ALERT>
I used vector calculus:
Consider the two vectors originating at the center of the earth that point to the two locations. The plane that is formed by these two vectors cuts the surface of the earth along the great circle through these two points. Now the angle that this plane makes with the plane containing the equator is the maximum latitude of the great circle (both on the northern and the southern hemisphere). There are some special cases to consider, and you also have to determine if the shortest path takes the northern or the southern route, but that's basicly the idea.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Thu Feb 17, 2005 1:49 pm

Oh yeah, thanks! :) My solution is not fair O(1) because that threshold of 1e-8 is related to value limit (minutes).

Also for my fractional form I think that the 2nd extreme will be somewhere outside the sphere (in case it exists), and thus outside (0;1) range. At least because your solution does not expect to test more than one mid-point so it can be considered as a proof.
To be the best you must become the best!

Post Reply

Return to “Volume 108 (10800-10899)”