Mowing the Field#10602
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. In fact, he only manages to move his mowing machine once per day. On day , he starts at position (x_1, y_1), and on day , he mows along a straight segment to 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.
FJ's progress is so slow that some of the grass he mows might grow back before he finishes all of his mowing. Any section of grass that is cut on day will grow back on day d+t. Thus, if FJ's mowing path crosses a path he cut at least days earlier, he will end up cutting the same section of grass again. In an effort to improve his poor mowing strategy, FJ would like to count the number of times this happens.
Count the number of times FJ's mowing path crosses an earlier segment of grass that has already grown back. You should only count "perpendicular" crossings, defined as a point common to a horizontal and a vertical segment that is not an endpoint of either segment.
The first line contains two integers and t~(2 \le n \le 10^5, 1 \le t \le n, and is even). The next lines describe the position of the mower on days 1, \ldots, n. The -th of these lines contains two integers x_i and y_i (nonnegative integers, each at most 10^9).
Print the number of crossing points described above, where FJ re-cuts a section of grass that has already grown back after being cut earlier.
In this example, on day , FJ crosses a segment of grass that he cut on day , which counts as one crossing. The other intersections do not count.
Example 1