## USACO 2016 January Contest, Platinum

## Problem 2. Mowing the Field

Contest has ended.

**Log in to allow submissions in analysis mode**

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.

#### INPUT FORMAT (file mowing.in):

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).

#### OUTPUT FORMAT (file mowing.out):

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.#### SAMPLE INPUT:

7 4 0 10 10 10 10 5 3 5 3 12 6 12 6 3

#### SAMPLE OUTPUT:

1

Here, FJ crosses on day 7 a segment of grass he cut on day 2, which counts. The other intersections do not count.

Note: This problem has expanded limits: 5 seconds per test case (10 for Python and Java), and 512 MB of memory.

Problem credits: Chad Waters and Brian Dean