[USACO16JAN]割草场Mowing the Field

题目描述

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. 临时翻译 农民约翰在管理他的农场的各个方面是相当可靠的，除了及时地修剪草。他设法每天只移动一次割草机。某1天，他开始在位置和一天他割沿直线段的位置，他可以在他农场的二维地图水平或垂直移动。FJ的水平和垂直移动之间交替连续几天。 所以越来越慢是FJ的进步，他可能在一些草长回来之前就割完了所有的草。草的任何部分（点）在一天内将重新长出来，所以如果FJ的割草路径穿过一条他在几天前割过了，他将不会在同一点再割草。在努力尝试和改革他可怜的修剪策略，FJ想知道需要的次数。 请算一下FJ的割草路径，使草不会再长出来。你只能计算“垂直”交叉点，定义为一个点在一个水平和一个垂直段之间的共同点 。 输入输出格式 输入格式： 输入的第一行包含（） 下一行描述了每天割草机在的位置。 这些行中包含整数和非负整数（最多1000000000个）。 输出格式： 请输出有几个割了不止1次的点。 输入输出样例 输入样例# 1： 7 4 0 10 10 10 10 5 3 5 3 12 6 12 6 3 输出样例# 1： 1 说明 在这里，FJ跨越7天的一段草被他剪了2天，计数。 其他交叉口不计数。 注：这个问题已经扩大了范围：每个测试点有5秒（10个python和java），512 MB的内存。

输入输出格式

输入格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

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.