||[Feb. 5th, 2005|04:39 pm]
I beat everybody today! :)|
http://plg.uwaterloo.ca/cgi-bin/cgiwrap/acm00/score2.cgi (same contest)
It was nice to code at home, instead of on the broken terminals in MC. Problem A was on the nasty side. I was lucky to notice all the tricky cases, and also to come up with a nice approach. For a long while I thought I would have to do all kinds of horrible 3D geometry, but I ended up just doing a 4-point binary search (or whatever one wants to call it) on the line segment joining A and B. Segment AB happens to lie on the great circle - how convenient! So for every point P on it, you can just extend OP to the edge of the great arc.