문제
파리 올림픽이 다가오고, 양궁팀 코치 정올이는 선수들을 훈련시키는 중이다. 그는 2차원 좌표 평면에서 다음과 같은 훈련을 준비했다.
N 개의 축에 평행한 직사각형 표적과4N 명의 양궁선수가 있다. 각 양궁선수는 서로 다른 표적의 꼭짓점에 배정되어야 한다.i 번째 순간(1 ≤ i ≤ N) 마다 다음이 발생한다:i 번 표적이 나타난다.해당 표적의 꼭짓점에 배정된
4 명의 양궁선수가 해당 꼭짓점을 겨냥해 화살을 쏜다.만약 양궁선수의 화살이 표적 꼭짓점에 도달하기 전에 표적 내부를 관통하거나 놓친다면, 양궁선수들은 훈련에 실패한다.
i 번째 표적은 다음 표적을 위해 사라진다.
각 양궁선수는
표적
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 은 동일하다.)
또한 각 양궁선수는 특정한 "집중" 각도를 유지해야 한다. 따라서 각 양궁선수는 특정 기울기로 화살을 쏜다. 양궁선수의 화살 궤적은
양궁팀 코치 정올이는 양궁선수들의 기술을 세심하게 관찰하고 싶어 하므로, 가장 멀리 떨어져 있는 양궁선수들 간의 거리를 최소화하고자 한다. 양궁선수를 각 표적 꼭짓점에 최적으로 배치했을 때,
입력
첫 번째 줄에는 테스트 케이스의 수
각 테스트 케이스는 다음과 같이 구성된다:
첫 번째 줄에는 두 개의 정수
N 과X_1 이 주어진다. (1 \le N \le 4 \cdot 10^4 )N 은 표적의 개수,X_1 은 표적의 왼쪽 가장자리x 좌표이다.
이후
N 개의 줄에는 각 줄마다 세 개의 정수y_1^{(i)}, y_2^{(i)}, x_2^{(i)} 가 주어진다.y_1^{(i)} : 표적의 하단y 좌표y_2^{(i)} 표적의 상단y 좌표x_2^{(i)} : 표적의 오른쪽x 좌표
마지막 줄에는
4N 개의 정수s_1, s_2, …,\ s_{4N} 이 주어진다.s_i 는 양궁선수i 의 화살 궤적의 기울기이다.
출력
각 테스트 케이스에 대해 양궁선수들이 가장 멀리 떨어져 있는 최소 거리를 출력하거나, 양궁선수들이 훈련에 성공하는 경우가 없다면
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 40점 | 모든 |
| #2 | 35점 | 모든 테스트 케이스에 대하여 |
| #3 | 25점 | 추가 제약 조건 없음 |
예제
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 -4
17
-1
11
첫 번째 테스트 케이스에 대한 최적 배치는 다음과 같다:
표적 꼭짓점에 대한 양궁선수 배정:
양궁선수 1: (6, 1)
양궁선수 2: (6, 3)
양궁선수 3: (3, 4)
양궁선수 4: (3, 6)
양궁선수 5: (1, 4)
양궁선수 6: (1, 3)
양궁선수 7: (1, 6)
양궁선수 8: (1, 1)
이 배치를 통해 양궁선수들이 위치할 y-좌표:
양궁선수 1:
y=−5y = -5y=−5 양궁선수 2:
y=9y = 9y=9 양궁선수 3:
y=−2y = -2y=−2 양궁선수 4:
y=12y = 12y=12 양궁선수 5:
y=1y = 1y=1 양궁선수 6:
y=6y = 6y=6 양궁선수 7:
y=2y = 2y=2 양궁선수 8:
y=5y = 5y=5
최적 거리 계산:
가장 멀리 떨어진 양궁선수 간의 거리는
따라서 최소 거리는 17이다.
두 번째 테스트 케이스가 불가능한 이유:
표적 1의 우상단 꼭짓점
그 이유는, 해당 꼭짓점을 겨냥하는 화살이 표적 내부를 관통하지 않고 도달하는 방법이 없기 때문이다. 따라서 양궁선수들은 훈련에 실패할 수밖에 없다.
로그인해야 코드를 작성할 수 있어요.