8507: BZOJ4507：[Usaco2016 Jan]Mowing the Field

农夫约翰在管理他的农场的各个方面都相当可靠，除了一条：他总是不能及时地割草。在第1天，他从位置（x1，y 1）开始，在第d天时，他沿着直线行走到位置（xd，yd），约翰总是在他农场的2D地图上水平或垂直移动;即xd =  xd-1或yd = yd-1。在这连续的几天里，FJ会交替着走水平线和竖直线。可是FJ的割草的进度太慢了，一些草可能 会在他完成所有割草之前重新长出来。在第d天切割的草的任何部分将在第d + T天的时候重新出现，因此如果FJ割 草的路径穿过他至少T天以前割过草的路径，他将再次在同一地点割草。 为了努力改革他的可怜的割草战略，FJ想 计算这种情况发生的次数。请计算FJ的割草路径穿过草已经生长的早期区段的次数。你应该只计算“垂直”交叉， 定义为水平线段和垂直线段之间的公共点，包括两者的端点。

输入格式

第一行输入包含N（2≤N≤100,000）和T（1≤T≤N，T是偶数）。 接下来的N行描述了在1...N天的割草机的位置。每行包含两个整数xi和yi（非负整数，每个最多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天他曾经切割过的一段草地。其他交叉点不计数

提示

没有写明提示

题目来源

Platinum 鸣谢g1n0st提供译文