Analysis: Hill walk by Nathan Pinsker

Since Bessie moves from left to right, it is fairly straightforward to realize that she can move across each hill at most once. This means that, if we can (quickly) find where Bessie will land after falling off another hill, we will have solved the problem.

Now consider what happens when Bessie falls off a hill at some location (p, q). There are some number of hills that cross the line x=p, but Bessie will fall onto the one that crosses it at the highest y-coordinate that is below q. This suggests that we will have to maintain some sort of ordering of hills, as we need to be able to distinguish between hills that are above Bessie at (p, q) and hills that are below her. Another thing we can notice is that the ordering of hills is enough by itself to solve the problem. If, when Bessie reaches the end of some hill, we have an ordering on hills by y-coordinate, we simply take the hill with y-coordinate directly below Bessie's hill as the one she must fall onto.

The key insight here is to use the fact that no two hills intersect. It's not completely obvious, but this means that the ordering of two specific hills in this way does not depend on x-coordinate: two hills cannot cross, so they cannot change positions. Furthermore, for a given x-coordinate this is a total ordering-- if we have three segments a, b, and c, and a < b and b < c, then a < c. (Here, we are using the '<' operator to denote one hill being below another.)

Now that we have a way to order hills, we will use a plane sweep to keep track of the hills as Bessie moves from left to right. At the start or end of each hill, we will add or remove that hill from a standard binary search tree. Since at all times we have an ordering on every hill in the tree, and since that ordering does not change as we move across the plane, the tree's state will remain correct. We keep track of Bessie's position, and record where she lands whenever the hill she is walking on ends. Processing the start and end of each hill takes O(log n) time in the worst case, so the runtime of this algorithm is O(n log n), which is fast enough.

Here is Travis' code: 

struct edge {
	int x1, y1, x2, y2, index;

	/* Intuitively, this orders segments from lowest to highest.
	
	   For two segments such that the interval [x1, x2] intersects
	   [o.x1, o.x2], this checks if the first segment is lower than
	   the second segment at x-coordinate x in that intersection.

	   This comparison induced a total ordering on all segments which
	   will be contained in the set (below) at any given time.
	   
	   Be careful to avoid integer overflow. */
	bool operator<(edge const& o) const {
		if (x2 < o.x2) {
			return (long long) (y2 - o.y1) * (long long) (o.x2 - o.x1) <
			       (long long) (o.y2 - o.y1) * (long long) (x2 - o.x1);
		} else {
			return (long long) (o.y2 - y1) * (long long) (x2 - x1) >
			       (long long) (y2 - y1) * (long long) (o.x2 - x1);
		}
	}
};
edge edges[NMAX];

struct event {
	int edgeIndex;
	int x, y;

	bool operator<(event const& o) const {
		if (x == o.x) {
			return y < o.y;
		}
		return x < o.x;
	}
};
event events[NMAX*2];

int main() {
#ifndef HOME
	freopen("hillwalk.in","r",stdin);
	freopen("hillwalk.out","w",stdout);
#endif

	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		edges[i].index = i;
		scanf("%d %d %d %d", &edges[i].x1, &edges[i].y1, &edges[i].x2, 
&edges[i].y2);
		events[2*i].edgeIndex = i;
		events[2*i].x = edges[i].x1;
		events[2*i].y = edges[i].y1;
		events[2*i+1].edgeIndex = i;
		events[2*i+1].x = edges[i].x2;
		events[2*i+1].y = edges[i].y2;
	}

	sort(events, events + (2*n));

	set s;
	s.insert(edges[0]);
	int currentEdge = 0;
	int totalCount = 1;

	for (int eindex = 1; eindex < 2*n; eindex++) {
		event ev = events[eindex];
		edge ed = edges[ev.edgeIndex];

		if (ev.x == ed.x1) {
			s.insert(ed);
		} else {
			if (ev.edgeIndex == currentEdge) {
				set::iterator iter = s.find(ed);
				assert(iter != s.end());
				if (iter == s.begin()) {
					break;
				}
				set::iterator iter2 = iter;
				--iter2;
				currentEdge = iter2->index;
				s.erase(iter);
				totalCount++;
			} else {
				s.erase(ed);
			}
		}

	}

	printf("%d\n", totalCount);
}