상자 안에서 생각하기

Data Co는 방대한 양의 측량 데이터를 정리하는 데 어려움을 겪고 있습니다. 지구의 넓은 영역에 걸친 수십 개의 측량 데이터 집합이 있으며, 각 측량의 범위는 경계 상자(bounding box)로 저장됩니다. 덕분에 특정 지역의 정보가 필요한 사람은 좌표만 입력하면 해당 데이터를 찾을 수 있습니다. 여러분이 할 일은 각 사용자 질의에 대해 어떤 저장된 측량 상자가 관련되어 있는지 찾는 것입니다.

첫 번째 줄에는 테스트 케이스의 수 $T$가 주어집니다. 각 테스트 케이스는 두 개의 경계 상자 목록으로 이루어집니다.

• 첫 번째 목록은 시스템에 저장된 경계 상자들, 즉 데이터 상자(Data Box) 입니다.
• 두 번째 목록은 사용자 질의를 나타내는 경계 상자들, 즉 질의 상자(Query Box) 입니다.

각 목록 앞에는 그 목록에 포함된 상자의 개수가 한 줄에 주어집니다. 하나의 경계 상자는 공백 하나로 구분된 두 개의 위도/경도 좌표로 한 줄에 표현됩니다.

위도1,경도1 위도2,경도2

첫 번째 좌표는 상자의 한 꼭짓점(위쪽 모서리)이고, 두 번째 좌표는 그 반대편 꼭짓점입니다. 위도와 경도는 도(degree) 단위로 주어집니다.

각 테스트 케이스마다, 하나 이상의 질의 상자와 어떤 식으로든 맞닿는 데이터 상자를 모두 출력합니다. 두 상자가 경계선이나 꼭짓점만 공유하더라도 맞닿은 것으로 간주합니다. 맞닿는 각 데이터 상자는 입력과 동일한 좌표로, 입력에 주어진 순서대로 정확히 한 번씩만 출력합니다. 여러 질의 상자가 같은 데이터 상자와 맞닿더라도 그 데이터 상자는 한 번만 출력합니다.

한 테스트 케이스에서 어떤 질의 상자와도 맞닿는 데이터 상자가 하나도 없으면 대신 No data found. 를 출력합니다.

연속한 테스트 케이스의 출력은 빈 줄 하나로 구분합니다.

위도와 경도는 각도로 나타내는 측정값입니다. 위도선은 지구를 가로지르는 수평선으로, 적도의 위도는 0, 북극은 90, 남극은 -90 입니다. 경도선(자오선)은 두 극 사이를 세로로 잇습니다. 본초 자오선의 경도는 0 이며, 경도는 동쪽으로 갈수록 증가하고 서쪽으로 갈수록 감소하다가 ±180 에서 한 바퀴 돌아 이어집니다(즉 180 과 -180 은 같은 자오선을 가리킵니다).

상자의 위도 범위는 극을 넘어가며 감싸지 않습니다. 그러나 상자의 경도 범위는 ±180 의 날짜변경선을 넘어 감쌀 수 있으며, 항상 첫 번째 좌표의 경도에서 두 번째 좌표의 경도까지 동쪽 방향으로 이어집니다. 예를 들어 두 좌표의 경도가 각각 170 과 -160 인 상자는 170 에서 동쪽으로 ±180 을 지나 -160 까지의 경도 범위를 덮습니다.