#PU601. USACO 2016 January Contest, Platinum — Problem 2. Mowing the Field

    ID: 1456 传统题 文件IO:mowing 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan16来源:usaco.orgscoring:equal_test_cases线段树平衡树

USACO 2016 January Contest, Platinum — Problem 2. Mowing the Field

USACO 2016 January Contest, Platinum — Problem 2. 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 (x1,y1)(x_1, y_1) and on day dd he mows along a straight segment to the position (xd,yd)(x_d, y_d), moving either horizontally or vertically on the 2D map of his farm; that is, either xd=xd−1x_d = x_{d-1}, or yd=yd−1y_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 dd will reappear on day d+Td + T, so if FJ's mowing path crosses a path he cut at least TT 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 NN (2≤N≤100,0002 \leq N \leq 100,000) and TT (1≤T≤N1 \leq T \leq N, TT even). The next NN lines describe the position of the mower on days 1…N1 \ldots N. The iith of these lines contains integers xix_i and yiy_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
Here, FJ crosses on day 7 a segment of grass he cut on day 2, which counts. The
other intersections do not count.

提示

Problem credits: Chad Waters and Brian Dean