찌그러진 바퀴

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

목공소가 언덕 기슭에 있다. 두 아이가 찌그러진 바퀴 모양의 나무토막을 가지고 논다. 이 나무토막은 두 면이 서로 합동인 볼록다각형인 납작한 나무 조각이다. 한 아이가 바퀴를 언덕 꼭대기에 올려놓고 굴려 내려보내면, 다른 아이는 바퀴가 최종적으로 멈출 위치를 미리 맞히려 한다. 여러분의 프로그램은 그 멈추는 위치를 계산해야 한다.

바퀴는 무게중심이 주어진 단순 볼록다각형으로, 언덕은 위에서 아래로 기울기가 엄격히 감소하는 선분들의 사슬로 모형화한다. 첫 번째(가장 위) 선분의 기울기는 양수이고, 마지막 선분은 수평(기울기 00)이다. 언덕의 가장 높은 지점은 첫 번째 선분의 오른쪽 끝점이며, 거기서부터 언덕은 왼쪽 아래로 내려간다. 이어지는 각 선분은 앞 선분보다 완만하고, 마지막 수평 선분은 바퀴가 그 끝을 벗어나지 않을 만큼 충분히 왼쪽으로 길게 뻗어 있다. 처음에 바퀴는 언덕과 적어도 한 점에서 닿도록 놓인다. 아래 그림에서 실선은 처음 위치, 점선은 마지막 위치이다.

운동은 하나의 규칙을 따른다. 매 순간 바퀴는 현재 언덕에 닿아 있는 꼭짓점 중 단 하나 PP를 축으로 하여, 무게중심의 yy좌표가 낮아지는 방향으로 회전한다. (매 순간 그런 꼭짓점은 많아야 하나뿐이다.) 바퀴의 다른 부분이 언덕에 닿을 때까지 PP를 축으로 계속 돌고, 닿는 순간 축을 다시 고른다. 어떤 접촉 꼭짓점을 축으로 삼아도 무게중심을 더 낮출 수 없게 되면 바퀴는 멈춘다. 무게중심을 어느 방향으로든 최대 10510^{-5}만큼 옮겨도 바퀴의 안정성은 바뀌지 않는다고 가정하며, 마찰이 충분히 커서 바퀴가 표면에서 미끄러지지 않고 오직 구르기만 한다고 가정한다.

입력

첫 줄에 테스트 케이스의 수 tt (1t101 \le t \le 10)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

첫 줄에 바퀴의 꼭짓점 수 nn (1n101 \le n \le 10)이 주어진다. 이어지는 nn개의 줄에는 각 꼭짓점의 처음 위치 xx, yy 좌표가 실수로 주어지며, 꼭짓점들은 다각형을 따라 도는 순서대로 나열된다. 그다음 줄에는 무게중심의 처음 xx, yy 좌표가 실수로 주어진다. 무게중심은 다각형의 내부 또는 경계 위에 있으며, 반드시 기하학적 무게중심(도형에서 계산되는 값)일 필요는 없다.

그다음 줄들은 언덕을 가장 가파른 선분부터 가장 완만한 선분 순서로 기술한다. 각 줄에는 한 선분의 길이와 기울기가 실수로 주어지며, 기울기는 엄격히 감소하고 마지막 선분의 기울기는 00이다. 마지막으로 한 줄에 첫 번째(가장 가파른) 선분의 오른쪽 끝점 xx, yy 좌표가 실수로 주어진다. 모든 좌표와 기울기는 실수이다.

출력

각 테스트 케이스마다 한 줄에 두 수를 출력한다. 바퀴가 최종적으로 멈춘 위치에서의 무게중심 xx, yy 좌표이며, 각각 소수점 아래 정확히 33자리로 반올림하고 공백 하나로 구분한다.