레이팅 미적용농부 존의 \(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 1000\)). 각 말뚝은 인접한 두 말뚝과 수직 또는 수평 선분인 울타리로 연결되어 있으므로, 전체 울타리는 변이 x축 또는 y축에 평행한 다각형으로 볼 수 있다 (마지막 말뚝은 첫 번째 말뚝과 다시 연결되어, 울타리가 목초지를 둘러싸는 닫힌 고리를 이룬다). 울타리 다각형은 "올바른" 형태로서, 울타리 선분들은 끝점에서만 겹칠 수 있고, 각 말뚝은 정확히 두 울타리 선분의 끝점과 일치하며, 한 끝점에서 만나는 두 울타리 선분은 서로 수직이다.
각 소는 매일 산책을 시작하는 위치와 끝내는 위치를 선호하는데, 두 위치 모두 울타리 위의 어떤 점이다 (말뚝일 수도 있고 아닐 수도 있다). 각 소는 매일 산책할 때 울타리를 따라 걸으며, 시작 위치에서 출발해 끝 위치에서 멈춘다. 울타리가 닫힌 고리를 이루므로 소가 택할 수 있는 경로는 두 가지이다. 소는 다소 게으른 동물이기 때문에, 각 소는 울타리를 도는 두 방향 중 더 짧은 방향으로 걷는다 (거리가 같다면 어느 방향이든 택할 수 있다).
각 소가 걷는 거리를 구하여라.
문제 제공: Brian Dean
배점
- 입력 2-6: \(0\le x,y \le 100\)이고 \(N\le 100\)
- 입력 7-11: 추가 제약 없음.
문제 제공: Brian Dean
첫째 줄에 \(N\)과 \(P\)가 주어진다. 다음 \(P\)개의 줄에는 시계 방향 또는 반시계 방향 순서로 울타리 말뚝의 위치를 나타내는 두 정수가 각각 주어진다. 다음 \(N\)개의 줄에는 소의 시작 위치 \((x_1, y_1)\)과 끝 위치 \((x_2, y_2)\)를 나타내는 네 정수 \(x_1\) \(y_1\) \(x_2\) \(y_2\)가 각각 주어진다.
각 소가 걷는 거리를 나타내는 \(N\)개의 정수를 출력한다.
5 4
0 0
2 0
2 2
0 2
0 0 0 2
0 2 1 0
2 1 0 2
1 0 1 2
1 2 1 02
3
3
4
4The first cow can walk directly from \((0,0)\) to \((0,2)\).
The second cow can walk from \((0,2)\) to \((0,0)\) and then to \((1,0)\).
The fourth cow has two possible routes with equal lengths:
\((1,0)\to (0,0)\to (0,2)\to (1,2)\) and \((1,0)\to (2,0)\to (2,2)\to (1,2)\).
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > US Open > Bronze