Mowing the Field

题目描述

农夫 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$（$2 \leq N \leq 100,000$）和 $T$（$1 \leq T \leq N$，且 $T$ 为偶数）。 接下来的 $N$ 行描述割草机在第 $1 \ldots N$ 天的位置。其中第 $i$ 行包含整数 $x_i$ 和 $y_i$（均为非负整数，且各自不超过 1,000,000,000）。

输出格式

请输出上述所描述的交叉点数量，即 FJ 在草已在先前被割掉并长回之后，再次割到同一点的次数。

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

1

提示

这里，FJ 在第 7 天与他在第 2 天割过的一段草发生相交，这一次应计入。其他相交都不计入。 注意：本题扩大了限制：每个测试用例 5 秒（Python 和 Java 为 10 秒），内存 512 MB。 题目贡献者：Chad Waters 和 Brian Dean

标签: USACO|2016|Platinum

来源

USACO|2016|Platinum