P3136 [USACO16JAN] Mowing the Field P

Farmer John 在管理农场的各个方面都相当可靠，除了一件事：他非常不擅长及时修剪草地。事实上，他每天只能移动一次割草机。在第 1 天，他从位置 $(x_1, y_1)$ 开始，在第 $d$ 天，他沿着一条直线段移动到位置 $(x_d, y_d)$，在农场的二维地图上，他要么水平移动，要么垂直移动；也就是说，要么 $x_d = x_{d-1}$，要么 $y_d = y_{d-1}$。FJ 在连续的日子里交替进行水平和垂直移动。 FJ 的进展非常缓慢，以至于在他完成所有修剪之前，一些被他修剪过的草可能会重新长出来。任何在第 $d$ 天被修剪的草会在第 $d + T$ 天重新长出来，因此如果 FJ 的修剪路径与至少 $T$ 天前修剪过的路径交叉，他将再次在同一位置修剪草地。为了尝试改进他糟糕的修剪策略，FJ 想要计算这种情况发生的次数。 请计算 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$。

输入的第一行包含 $N$（$2 \leq N \leq 100,000$）和 $T$（$1 \leq T \leq N$，$T$ 为偶数）。 接下来的 $N$ 行描述了割草机在第 $1$ 到第 $N$ 天的位置。第 $i$ 行包含整数 $x_i$ 和 $y_i$（每个为非负整数，且不超过 $1,000,000,000$）。

请输出上述交叉点的数量，即 FJ 重新修剪已经重新长草的点的次数。

在这里，FJ 在第 7 天与他在第 2 天修剪的草地路径交叉，这算作一次。其他交叉点不算。 注意：本题有扩展的限制：每个测试用例 5 秒（Python 和 Java 为 10 秒），内存限制为 512 MB。