시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB111100.000%

문제

One of the iconic signs of the 1960s protest movement was the peace sign, shown in the picture below on the left side. On the right, you see (a rotated, scaled version of) the sign for Mercedes Benz, a manufacturer of luxury cars. The similarity between the two has been noted often, and some of the protesters in the 1968 movements have been accused of trading the left sign for the right in their own lives.

Without analyzing whether former protesters ended up being more economically successful — or less socially progressive — later in life than their contemporaries, we will instead focus here on the much more important question how to determine how similar two line drawings are. You will be given two drawings, each consisting of some number of straight lines (no circles). The similarity is the total number of lines in the second image you can exactly match by taking the first image, and doing a combination of (1) translating it some combination of up/down/right/left, (2) rotating it by some angle, and (3) scaling it by some factor. For example, in the given picture (without the circle), you can rotate the left picture 90 degrees to the right, shift it to the right, and scale it by 75%, and match three lines.

입력

The first line is the number K of input data sets, followed by the K data sets, each of the following form:

The first line of the data set contains two integers 1 ≤ n, n′ ≤ 50, the number of lines in the first and second image. This is followed by a line with 4n doubles 0.0 ≤ xi,1, yi,1, xi,2, yi,2 ≤ 100.0; the i th line in the first image goes from (xi,1, yi,1) to (xi,2, yi,2). Next is a line with 4n′ doubles 0.0 ≤ x′i,1 , y′i,1 , x′i,2 , y′i,2 ≤ 100.0; these describe the n′ lines of the second image in the same way.

출력

For each data set, output “Data Set x:” on a line by itself, where x is its number. Then output the maximum number of lines in the second image you can match by translating, rotating, and scaling the first image. Our inputs will be such that tiny rounding errors of less than 0.00001 will not affect the results.

Each data set should be followed by a blank line.

예제 입력 1

4
4 3
3 3 3 1 3 3 3 5 3 3 4.73205 2 3 3 1.26795 2
2.5 2.5 4 2.5 2.5 2.5 1.75 3.79904 2.5 2.5 1.75 1.20096
3 3
0 1 3 1 0 2 2 2 0 0 1 0
0 1 3 1 0 2 1 2 0 0 2 0
3 3
0 1 3 1 0.5 2 2.5 2 1 0 2 0
0 1 3 1 1 2 2 2 0.5 0 2.8 0
2 4
0 1 2 1 1 0 1 2
0 1 1 1 1 1 2 1 1 0 1 1 1 1 1 2

예제 출력 1

Data Set 1:
3

Data Set 2:
1

Data Set 3:
2

Data Set 4:
1