레이팅 미적용농부 존은 농장 관리의 모든 면에서 상당히 믿음직하지만, 딱 한 가지 예외가 있다. 제때 풀을 깎는 데는 형편없다는 것이다. 실제로 그는 하루에 한 번밖에 잔디 깎는 기계를 옮기지 못한다. 1일째에 위치 \((x_1, y_1)\)에서 시작하여, \(d\)일째에는 위치 \((x_d, y_d)\)까지 직선 구간을 따라 풀을 깎으며 이동하는데, 농장의 2차원 지도에서 수평 또는 수직으로만 이동한다. 즉, \(x_d = x_{d-1}\)이거나 \(y_d = y_{d-1}\)이다. 농부 존은 날마다 수평 이동과 수직 이동을 번갈아 한다.
농부 존의 진행이 너무 느려서, 그가 깎은 풀 중 일부는 모든 풀 깎기가 끝나기 전에 다시 자랄 수도 있다. \(d\)일째에 깎인 풀은 \(d + T\)일째에 다시 자라나므로, 농부 존의 경로가 최소 \(T\)일 이전에 깎았던 경로를 가로지르면 같은 지점의 풀을 다시 깎게 된다. 자신의 부실한 풀 깎기 전략을 개선하기 위해, 농부 존은 이런 일이 몇 번 일어나는지 세고 싶다.
농부 존의 경로가 풀이 이미 다시 자란 이전 구간을 가로지르는 횟수를 세어라. "수직 교차"만 세어야 하는데, 이는 수평 구간과 수직 구간의 공통점 중 어느 쪽의 끝점도 아닌 점으로 정의된다.
출제자: Chad Waters and Brian Dean
출제자: Chad Waters and Brian Dean
입력의 첫째 줄에 \(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 이하의 음이 아닌 정수).
위에서 설명한 교차점, 즉 농부 존이 이전에 깎았다가 다시 자란 풀을 다시 깎게 되는 지점의 개수를 출력한다.
mowing.in · 출력을 쓸 파일 mowing.out7 4
0 10
10 10
10 5
3 5
3 12
6 12
6 31Here, 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.
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > January > Platinum