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);
}