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!

[Per]

There are infinitely many great circles passing through the two cities in that sample case, since the two points are antipodal.

[..]

Oh thanks.....
Seems I am making mistake in my code......

[misof]

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]

Another interesting case:

Code: Select all

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

[gvcormac]

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]

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.

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]

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.

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]

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]

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]

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]

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]

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

[little joey]

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]

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.