레이팅 미적용참고: 이 문제의 시간 제한은 기본의 1.25배인 2.5초이다.
참고: 이 문제에서 다루는 정수가 매우 클 수 있으므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있다.
파리 무림픽이 다가오고 있어 농부 존은 소들로 이루어진 양궁 팀을 훈련시키고 있다! 그는 2차원 좌표 평면에서 다음과 같은 훈련을 준비했다.
축에 평행한 직사각형 과녁 \(N (1 \leq N \leq 4 \cdot 10^4)\)개와 소 \(4N\)마리가 있다. 모든 소는 서로 다른 과녁 꼭짓점에 배정되어야 한다. \(1 \leq i \leq N\)에 대해, 순간 \(i\)에 다음이 일어난다.
- 과녁 \(i\)가 나타난다.
- 그 꼭짓점들에 배정된 소 \(4\)마리가 자신의 꼭짓점을 향해 쏜다.
- 어떤 소의 화살이 배정된 꼭짓점에 맞거나 빗나가기 전에 과녁의 내부를 통과하면, 소들은 훈련에 실패한다.
- 다음 과녁을 위해 과녁이 사라진다.
각 소는 \(y\)축 \((x = 0)\) 위에 있고, 각 과녁은 직사각형으로 과녁 \(i\)의 왼쪽 아래 좌표는 \((X_1, y_1^{(i)})\), 오른쪽 위 좌표는 \((x_2^{(i)}, y_2^{(i)})\)이다. 좌표는 \(1 \leq X_1 < x_2^{(i)}\leq 10^9\)와 \(1 \leq y_1^{(i)} < y_2^{(i)} \leq 10^9\)를 만족한다 (참고: \(X_1\)은 모든 과녁에서 같다).
또한 각 소에게는 연습 중인 "집중" 각도가 있다. 따라서 쏠 때 특정 각도로 몸을 돌린다. 화살이 소의 위치에서 배정된 꼭짓점을 향해 직선으로 날아간다고 할 때, 소 \(i\)의 화살의 궤적은 그 기울기 \(s_i\) \((0 < |s_i| < 10^9)\)로 나타낼 수 있다.
소들의 자세를 꼼꼼히 살펴보기 위해, 농부 존은 가장 멀리 떨어진 두 소 사이의 거리를 최소화하고 싶다. 농부 존이 각 소를 과녁 꼭짓점에 최적으로 배정하고 \(y\)축 위에 배치한다면, 가장 멀리 떨어진 두 소 사이의 최소 거리가 얼마인지, 또는 소들이 어떻게 해도 훈련에 실패하는지 판정하는 것을 도와주자.
각 입력은 \(T\) (\(1 \leq T \leq 10\))개의 독립적인 테스트 케이스를 포함한다. 모든 테스트 케이스에 대한 \(N\)의 합이 \(4\cdot 10^4\)를 넘지 않음이 보장된다.
출제: Suhas Nagar
배점
- 입력 2: 모든 \(1 \leq i \leq 4N\)에 대해 \(|S_i|\)가 같다.
- 입력 3-9: 모든 테스트 케이스에 대한 \(N\)의 합이 최대 \(1000\)이다.
- 입력 10-15: 추가 제약 없음.
출제: Suhas Nagar
첫째 줄에 독립적인 테스트 케이스의 개수 \(T\) (\(1 \leq T \leq 10\))가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.
각 테스트 케이스의 첫째 줄에 과녁의 개수 \(N\)과 과녁의 가장 왼쪽 \(x\)좌표 \(X_1\)이 주어진다.
이어서 \(N\)개의 줄이 주어지며, \(i\)번째 줄에는 \(i\)번째 과녁의 아래쪽 \(y\)좌표, 위쪽 \(y\)좌표, 오른쪽 \(x\)좌표인 세 정수 \(y_1^{(i)}\), \(y_2^{(i)}\), \(x_2^{(i)}\)가 주어진다.
마지막 줄에 \(4N\)개의 정수 \(s_1, s_2, \dots, s_{4N}\)이 주어진다. \(s_i\)는 소 \(i\)의 화살 궤적의 기울기이다.
가장 멀리 떨어진 두 소 사이의 최소 가능한 거리를 출력하거나, 소들이 어떻게 해도 훈련에 실패한다면 \(-1\)을 출력한다.
3
2 1
1 3 6
4 6 3
1 -1 2 -2 3 -3 4 -4
2 1
1 3 6
4 6 3
1 1 2 2 3 3 4 4
2 1
1 3 3
4 6 3
1 -1 2 -2 3 -3 4 -417
-1
11One optimal assignment for test case 1 is the following target vertices for cows
1-8 respectively:
$$ (6, 1), (6,3), (3,4), (3,6), (1,4), (1,3), (1,6), (1,1) $$
This gives the following \(y\) locations for cows 1-8 respectively:
$$ -5, 9, -2, 12, 1, 6, 2, 5 $$
This gives a minimum distance of \(12-(-5) = 17\).
One reason the second test case is impossible is because it is impossible to
shoot the vertex at \((6, 3)\) (the top right vertex of target 1) without the shot
passing through the interior of target 1.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > February > Silver