Farmer John is quite reliable in all aspects of managing his farm, except one:
he is terrible at mowing the grass in a timely fashion. He only manages to
move the mowing machine once per day, in fact. On day 1, he starts at position
\((x_1, y_1)\) and on day \(d\) he mows along a straight segment to the position
\((x_d, y_d)\), moving either horizontally or vertically on the 2D map of his
farm; that is, either \(x_d = x_{d-1}\), or \(y_d = y_{d-1}\). FJ alternates
between horizontal and vertical moves on successive days.

So slow is FJ's progress that some of the grass he mows might grow back before
he is finished with all his mowing. Any section of grass that is cut in day \(d\)
will reappear on day \(d + T\), so if FJ's mowing path crosses a path he cut at
least \(T\) days earlier, he will end up cutting grass at the same point again.
In an effort to try and reform his poor mowing strategy, FJ would like to count
the number of times this happens.

Please count the number of times FJ's mowing path crosses over an earlier
segment on which grass has already grown back. You should only count
"perpendicular" crossings, defined as a point in common between a horizontal and
a vertical segment that is an endpoint of neither.

Problem credits: Chad Waters and Brian Dean

Problem credits: Chad Waters and Brian Dean

The first line of input contains \(N\) (\(2 \leq N \leq 100,000\)) and \(T\)
(\(1 \leq T \leq N\), \(T\) even).

The next \(N\) lines describe the position of the mower on days \(1 \ldots N\). The
\(i\)th of these lines contains integers \(x_i\) and \(y_i\) (nonnegative integers
each at most 1,000,000,000).

Please output a count of the number of crossing points described above, where FJ
re-cuts a point of grass that had grown back after being cut earlier.

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > January > Platinum