题目描述

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.

输入格式

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.

题目大意

FJ 在给农场除草。

FJ 第一天位于坐标 $(x_1,y_1)$，此后的每一天，FJ 都会水平或竖直地移动到另一个坐标并除去其上的草。具体而言：我们认为 $(x,y)\rightarrow (x+k,y)$ 视为一次水平移动，$(x,y)\rightarrow (x,y+k)$ 视为一次竖直移动。

FJ 在连续的两天内不会使用同一种移动方式进行移动，即 FJ 使用水平移动以及竖直移动是交替的。

FJ 在第 $d$ 天除去的草会在 $d+T$ 天再次生长出来，其中 $T$ 是一个偶数。

如果某次移动与先前的另外一次移动垂直交叉（即其中一个是水平移动，另外一个是竖直移动）且满足先前一次除去的草已经再次生长，那么就产生一次计数。

FJ 想知道，按照当前计划进行除草会产生多少次计数。

形式化题意

现给出 $n$ 个点，其中，第 $i$ 个点和第 $i+1$ 个点相连必定构成一条水平或竖直的线段，记为线段 $i$。显然线段 $i$ 必定与线段 $i+1$ 共用一个端点。

额外保证线段 $i$ 必定与线段 $i+1$ 垂直。

对于某条线段 $d$，你需要统计出线段 $1\cdots d-T$ 中有多少条与线段 $d$ 相交且垂直，记为 $f_d$。

输出 $ans$，其中 $ans=\sum_{i=1}^{n-1} f_i$。

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

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.