레이팅 미적용*참고: 이 문제의 시간 제한과 메모리 제한은 3초와 512MB로, 각각 기본의 1.5배와 2배이다.*
농부 존의 \(N\)마리 소들(\(1 \leq N \leq 10^5\))은 각자 목초지를 둘러싼 울타리를 따라 매일 산책하는 것을 좋아한다. 안타깝게도 소가 울타리 말뚝 옆을 지나갈 때마다 말뚝에 몸을 비비기 때문에, 농부 존은 말뚝을 주기적으로 다시 칠해야 한다.
울타리는 \(P\)개의 말뚝(\(4 \leq P \leq 2\cdot 10^5\), \(P\)는 짝수)으로 이루어져 있으며, 각 말뚝의 위치는 농부 존의 농장 지도 위의 서로 다른 2차원 점 \((x,y)\)이다 (\(0 \leq x, y \leq 10^9\)). 각 말뚝은 인접한 두 말뚝과 수직 또는 수평 선분인 울타리로 연결되어 있으므로, 전체 울타리는 변이 x축 또는 y축에 평행한 다각형으로 볼 수 있다 (마지막 말뚝은 첫 번째 말뚝과 다시 연결되어, 울타리가 목초지를 둘러싸는 닫힌 고리를 이룬다). 울타리 다각형은 "올바른" 형태로서, 울타리 선분들은 끝점에서만 겹칠 수 있고, 각 말뚝은 정확히 두 울타리 선분의 끝점과 일치하며, 한 끝점에서 만나는 두 울타리 선분은 서로 수직이다.
각 소는 매일 산책을 시작하는 위치와 끝내는 위치를 선호하는데, 두 위치 모두 울타리 위의 어떤 점이다 (말뚝일 수도 있고 아닐 수도 있다). 각 소는 매일 산책할 때 울타리를 따라 걸으며, 시작 위치에서 출발해 끝 위치에서 멈춘다. 울타리가 닫힌 고리를 이루므로 소가 택할 수 있는 경로는 두 가지이다. 소는 다소 게으른 동물이기 때문에, 각 소는 울타리를 도는 두 방향 중 더 짧은 방향으로 걷는다. 놀랍게도 이 선택은 항상 명확하다 — 거리가 같은 경우는 없다!
소가 말뚝 옆을 지나가거나, 말뚝이 산책의 시작점 또는 끝점인 경우 소가 그 말뚝을 건드린다. 농부 존이 다음에 어느 말뚝을 다시 칠해야 할지 알 수 있도록, 각 울타리 말뚝이 하루에 몇 번 건드려지는지 계산하는 것을 도와주자.
모든 말뚝의 위치가 주어지면 울타리의 가능한 형태는 정확히 하나임을 증명할 수 있다.
문제 제공: Brian Dean
배점
- 입력 4-6: \(N,P\le 1000\)
- 입력 7-9: 모든 위치가 \(0\le x, y\le 1000\)을 만족한다.
- 입력 10-15: 추가 제약 없음.
문제 제공: Brian Dean
첫째 줄에 \(N\)과 \(P\)가 주어진다. 다음 \(P\)개의 줄에는 울타리 말뚝의 위치를 나타내는 두 정수가 특별한 순서 없이 각각 주어진다. 다음 \(N\)개의 줄에는 소의 시작 위치 \((x_1, y_1)\)과 끝 위치 \((x_2, y_2)\)를 나타내는 네 정수 \(x_1\) \(y_1\) \(x_2\) \(y_2\)가 각각 주어진다.
각 울타리 말뚝이 건드려지는 횟수를 나타내는 \(P\)개의 정수를 출력한다.
5 4
3 1
1 5
3 5
1 1
2 1 1 5
1 5 3 4
3 1 3 5
2 1 2 1
3 2 3 31
2
2
1The following posts are connected by fence segments:
$$ (3,1)\leftrightarrow (3, 5) \leftrightarrow (1,5) \leftrightarrow (1,1) \leftrightarrow (3,1) $$
The posts touched by each cow are as follows:
- Posts \(2\) and \(4\).
- Posts \(2\) and \(3\).
- Posts \(1\) and \(3\).
- No posts.
- No posts.
2 8
1 1
1 2
0 2
0 3
0 0
0 1
2 3
2 0
1 1 2 1
1 0 1 31
0
0
0
1
1
1
21 12
0 0
2 0
2 1
1 1
1 2
3 2
3 3
1 3
1 4
2 4
2 5
0 5
2 2 0 21
1
1
1
1
0
0
0
0
0
0
0riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > US Open > Silver