blackbee4   1년 전

많은 대중교통 시스템에는 원하는 경로를 파악하기 위한 온라인 인터페이스가 있습니다. 좋은 사용자 인터페이스 디자인의 한 가지 원칙은 시스템이 모든 관련 정보를 보여주되, 그 이상은 보여주지 않아야 한다는 것입니다. 이는 사용자가 중요한 부분에 집중할 수 있도록 하기 위함입니다.

시스템 지도를 보여주는 그래픽 사용자 인터페이스의 경우, 이는 당신이 지날 모든 역을 포함하되, 가능한 한 적은 수의 추가 역을 포함하는 지도를 보여주는 것을 의미합니다. 한편, 대부분의 사용자들은 균일한 축척의 직사각형 지도에 익숙하므로, 우리는 이 방식을 고수할 것입니다.

따라서 문제가 좀 더 구체화됩니다. 당신에게는 시스템 내 모든 역의 위치가 (x, y) 좌표로 주어집니다. 그런 다음, 당신이 이용할 노선이 지나는 역들의 목록(순서대로)도 주어집니다.

당신은 당신의 전체 여정을 포함하는 가장 작은 직사각형 안에 총 몇 개의 역이 포함되는지 계산해야 합니다.

입력

첫 번째 줄에는 데이터 세트의 수 K가 포함됩니다. 그 뒤에 K개의 데이터 세트가 다음 형식으로 이어집니다.

첫 번째 줄에는 두 개의 정수 n, m이 포함됩니다.

2 <= n <= 500은 시스템 내 전체 역의 수입니다.

2 <= m <= n은 당신이 여행할 역의 수입니다.

다음 $n$개의 줄은 i번째 역의 좌표인 정수 쌍 xi, yi를 제공합니다.

그 다음 줄은 당신이 방문할 m개의 역을 순서대로 나타내는 m개의 정수를 포함합니다. (여기서 정수 i는 i번째 역의 좌표를 참조합니다.)

출력

각 데이터 세트에 대해, 먼저 한 줄에 "Data Set x:"를 출력합니다. 여기서 x는 해당 데이터 세트의 번호입니다.

다음으로, 당신의 전체 여정을 포함하는 가장 작은 직사각형 안에 보이는 총 역의 수를 출력합니다.

각 데이터 세트 뒤에는 빈 줄 하나가 이어져야 합니다.

댓글을 작성하려면 로그인해야 합니다.