별자리 그리기

크기가 $(X+1) \times (Y+1)$ 인 격자가 있다. 이 격자의 맨 왼쪽 아래 격자점의 좌표는 $(0, 0)$이고, 맨 오른쪽 위 격자점의 좌표는 $(X, Y)$다.

이 격자 위에 별자리 그림이 그려져 있다. 이 별자리 그림은 $L$ 개의 빨간색 선분으로 되어 있고, 각 선분의 양 끝점은 모두 격자점 위에 있다.

별자리 그림과 별개로 $N$ 개의 별이 격자점에 놓여 있고, 이들 중 두 개의 별을 잇는 $M$ 개의 노란색 선분이 있다.

아래의 그림은 $X = 17$, $Y = 14$인 격자에서 $4$ 개의 빨간색 선분으로 구성된 별자리를 보여준다. 또한, $5$ 개의 별이 격자점에 놓여 있고, $6$ 개의 노란색 선분이 어느 별이 어떻게 연결되어 있는지를 보여준다. 즉, $L = 4$, $N = 5$, $M = 6$이다.

여러분은 별을 끌어 다른 격자점 위로 움직일 수 있다. 이 과정에서 두 별이 겹치면 안 된다. 노란색 선분의 끝점은 별의 위치를 따라가기 때문에, 별들이 움직이면 노란색 선분도 같이 움직인다.

여러분은 별을 움직여서 별에 연결된 노란색 선분이 만드는 그림이 빨간색 선분으로 그려진 별자리 그림과 일치되도록 해야 한다. 첫 그림의 $5$ 개의 별을 위의 그림처럼 옮기면 노란색 선분이 그리는 그림이 정확하게 별자리 그림과 같아짐을 알 수 있다.

여러분은 가능하면 별이 이동한 거리의 합 $R$을 가능한 작게 해야 한다.

초기에 $(x, y)$에 놓여있던 별이 $(\Delta x, \Delta y)$만큼 움직여서 최종 위치가 $(x + \Delta x, y + \Delta y)$라면, 이 별이 이동한 거리는 $\sqrt{ ( \Delta x \times \Delta x ) + ( \Delta y \times \Delta y ) }$이다.

입력 형식

첫 줄에 격자의 크기를 나타내는 두 정수 $X$와 $Y$가 공백으로 구분되어 주어진다. ($2 \le X, Y \le 50$)

그다음 줄에 빨간색 선분의 수 $L$이 주어진다. ($1 \le L \le 200$)

이어지는 $L$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 빨간색 선분에 대한 정보를 나타내는 네 정수 $A_i$, $B_i$, $C_i$, $D_i$가 공백으로 구분되어 주어진다. 이는 $i$ 번째 빨간색 선분의 양 끝점의 좌표가 $(A_i, B_i)$와 $(C_i, D_i)$임을 의미한다.

그다음 줄에 별의 수 $N$이 주어진다. ($2 \le N \le 300$)

이어지는 $N$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 별에 대한 정보를 나타내는 두 정수 $E_i$와 $F_i$가 공백으로 구분되어 주어진다. 이는 $i$ 번째 별이 초기에 $(E_i, F_i)$에 위치함을 의미한다. ($0 \le E_i \le X;$ $0 \le F_i \le Y$)

그다음 줄에 노란색 선분의 수 $M$이 주어진다. ($1 \le M \le 300$)

이어지는 $M$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 연결된 두 별의 정보를 나타내는 두 정수 $G_i$와 $H_i$가 공백으로 구분되어 주어진다. 이는 $i$ 번째 노란색 선분에 연결된 두 별의 번호를 의미한다. ($1 \le G_i, H_i \le N;$ $G_i \ne H_i$)

출력 형식

$N$ 개의 줄에 답을 출력한다.

$i$ 번째 줄에 $i$ 번째 별이 옮겨진 위치를 나타내는 두 정수 $E'_i$, $F'_i$를 공백으로 구분하여 출력한다. 이는 $i$ 번째 별이 $(E_i, F_i)$에서 $(E'_i, F'_i)$로 이동했음을 의미한다.

예제

17 14
4
1 2 10 2
1 2 1 10
10 2 1 10
1 10 9 12
5
6 3
8 8
9 11
12 11
15 0
6
1 2
1 5
2 5
2 3
3 4
2 4

1 2
1 10
5 11
9 12
10 2

채점 방식

이 문제는 풀이 소스 코드를 제출하지 않고, 각 테스트 케이스의 입력 데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

이 문제의 총점은 모든 미션의 점수의 합으로 계산된다. 각 미션의 점수를 계산하는 방법은 다음과 같다.

• $S$ : 미션의 만점
• $P$ : 미션에 대한 참가자의 점수
• $\alpha$, $\beta$ : 미션마다 정해진 상수
• $\alpha$ : 이동 거리 점수에서 만점을 받을 수 있는 총 이동 거리
• $\beta$ : 이동 거리 점수에서 만점의 $1/3$을 받을 수 있는 총 이동 거리

먼저, 별자리 점수 $P_\text{star}$는 다음과 같이 계산된다.

• $l_\text{input}$ : 주어진 별자리 그림의 길이
• $l_\text{output}$ : 참가자가 그린 그림의 길이
• $l_\text{common}$ : 주어진 별자리 그림과 참가자의 그림에서 겹치는 부분의 길이
• $\displaystyle P_\text{star} = \max\left\{ 0, 40 \times \frac{l_\text{input} - l_\text{output} + 2 \times l_\text{common}}{2 \times l_\text{input}} \right\}$

다음으로, 이동 거리 점수 $P_\text{move}$는 다음과 같이 계산된다.

1. $R \le \alpha$ 인 경우: $P_\text{move} = 30$
2. $\alpha < R \le \beta$ 인 경우: $\displaystyle P_\text{move} = 10 + 20 \times \left( \frac{ \beta - R }{ \beta - \alpha } \right)^2$
3. $R \ge \beta$ 인 경우: $P_\text{move} = 10 \times ( \beta / R )^2$

이때, 참가자의 점수 $P$는 이러하다.

1. 참가자의 그림이 주어진 별자리 그림과 완벽하게 일치하는 경우: $P = S \times \left( P_\text{star} + 2 \times P_\text{move} \right) / 100$
2. 그렇지 않은 경우: $P = S \times \left( P_\text{star} + P_\text{move} \right) / 100$

이후, $P$는 최종적으로 $0.1$ 단위로 버림된다.

단, 참가자의 출력이 올바르지 않은 경우 (출력 형식을 맞추지 않았거나, 제약 조건을 지키지 않는 등) $P = 0$이다.

각 미션의 정보는 다음과 같다.

미션마다 만점을 받을 수 있는 출력이 존재함이 보장된다.

해설