Let's Play Curling
시간 제한1초메모리 제한512 MB
수직선 위에 놓인 빨강 돌과 파랑 돌의 위치가 주어질 때, 모든 파랑 돌보다 c에 더 가까운 빨강 돌의 수가 최대가 되는 중심 c를 찾아 그 최댓값을 구하거나 불가능하면 Impossible을 출력한다.
문제
컬링은 선수들이 얼음판 위에서 스톤을 목표 영역을 향해 미끄러뜨리는 스포츠이다. 목표 영역의 중심에 가장 가까운 스톤을 가진 팀이 경기에서 승리한다.
두 팀 Red와 Blue가 수직선 위에서 겨루고 있다. 경기가 끝난 뒤 수직선 위에는 개의 스톤이 남아 있고, 그중 개는 Red 팀, 나머지 개는 Blue 팀의 것이다. Red 팀의 번째 스톤은 에, Blue 팀의 번째 스톤은 에 있다.
목표 영역의 중심 위치를 라 하자. 위 설명에서 알 수 있듯이, 인 어떤 가 존재하여 모든 에 대해 이면 Red가 경기에서 승리한다. 또한 이 조건을 만족하는 의 개수가 정확히 개이면 Red가 점을 얻는다고 한다.
Red 팀과 Blue 팀 스톤의 위치가 주어질 때, Red가 승리하면서 최대한 많은 점수를 얻도록 목표 영역의 중심 위치 를 정해야 한다. 는 정수일 필요가 없고 어떤 실수든 될 수 있다.
입력
입력은 여러 테스트 케이스로 이루어진다. 입력의 첫 줄에는 테스트 케이스의 개수를 나타내는 정수 가 주어진다. 각 테스트 케이스는 다음과 같다.
첫 줄에는 Red의 스톤 개수와 Blue의 스톤 개수를 나타내는 두 정수 과 이 주어진다. ()
둘째 줄에는 Red의 스톤 위치를 나타내는 개의 정수 이 주어진다. ()
셋째 줄에는 Blue의 스톤 위치를 나타내는 개의 정수 이 주어진다. ()
의 합과 의 합은 각각 를 넘지 않는다.
출력
각 테스트 케이스마다 한 줄을 출력한다. Red가 승리하면서 최대한 많은 점수를 얻도록 하는 가 존재하면 Red가 얻을 수 있는 최대 점수를 나타내는 정수 하나를 출력한다. (가 아니다.) 그렇지 않으면 "Impossible"을 큰따옴표 없이 출력한다.
힌트
첫 번째 예시 테스트 케이스에서는 로 두면 위치 2와 3에 있는 Red의 스톤이 득점한다.
두 번째 예시 테스트 케이스에서는 로 두면 위치 5와 7에 있는 Red의 스톤이 득점한다.