야구에서 '스트라이크 존'은 타자가 배트를 휘두르지 않았다는 전제 하에, '스트라이크' 판정을 받기 위해 야구공이 반드시 지나가야 하는 공간을 의미한다. 만약 타자가 배트를 휘두르지 않았을 때 야구공이 스트라이크 존을 피해 갔다면, '볼' 판정을 받는다. <그림 H.1>은 한 경기 중에 야구공 추적기가 기록한 야구공의 2차원 평면 상의 위치를 보여준다. 해당 그림에서 파란색 점은 스트라이크 판정을 받았으며, 빨간색 점은 볼 판정을 받았다. 이처럼 한 경기에서 기록된 야구공의 위치 데이터를 분석함으로써, 해당 경기의 스트라이크 존을 나타내는 직사각형 영역을 정의할 수 있게 된다.
<그림 H.1> - 한 경기에서 기록된 야구공의 2차원 평면에서의 위치 정보. 파란 점은 스트라이크, 빨간 점은 볼 판정을 받았다. 그림 생략.
여러분은 2차원 평면 상의 점으로 구성된 2개의 집합 P1, P2와 2개의 양의 정수 c1, c2를 입력받는다. R을 모든 변이 x축과 y축에 평행한 직사각형이라 하고, s를 P1 ∩ R에 속하는 점의 개수, b를 P2 ∩ R에 속하는 점의 개수로 정의하자. 이때 함수 eval(R) = c1 × s - c2 × b의 값이 최댓값이 되게 하는 직사각형 R을 찾는 프로그램을 작성하시오.
--------
[입력]
입력은 표준 입력을 사용한다.
입력의 첫 줄에는 P1에 속하는 점의 개수를 나타내는 정수 n1 (1 ≤ n1 ≤ 1,000)이 주어진다. 다음 n1개 줄에서는 P1에 속하는 점의 좌표를 나타내는 2개의 정수 x, y (-109 ≤ x, y ≤ 109)가 각각 주어진다. 각 점의 좌표는 (x, y)로 표현할 수 있다.
그 다음 줄에는 P2에 속하는 점의 개수를 나타내는 정수 n2 (1 ≤ n2 ≤ 1,000)가 주어진다. 다음 n2개 줄에서는 P2에 속하는 점의 좌표를 나타내는 2개의 정수 x, y (-109 ≤ x, y ≤ 109)가 각각 주어진다.
집합 P1 ∪ P2에 속하는 점에서 어떠한 두 점도 완전히 같은 좌표에 위치하지 않는다. 즉, 모든 점은 서로 다른 좌표에 위치함이 보장되어 있다.
입력의 마지막 줄에는 2개의 정수 c1, c2 (1 ≤ c1, c2 ≤ 10,000)가 주어진다.
--------
[출력]
출력은 표준 출력을 사용한다. 입력으로 주어진 P1, P2, c1, c2에 대해 eval(R)의 최댓값을 한 줄에 출력한다.
moner_ari 9달 전
[문제]
야구에서 '스트라이크 존'은 타자가 배트를 휘두르지 않았다는 전제 하에, '스트라이크' 판정을 받기 위해 야구공이 반드시 지나가야 하는 공간을 의미한다. 만약 타자가 배트를 휘두르지 않았을 때 야구공이 스트라이크 존을 피해 갔다면, '볼' 판정을 받는다. <그림 H.1>은 한 경기 중에 야구공 추적기가 기록한 야구공의 2차원 평면 상의 위치를 보여준다. 해당 그림에서 파란색 점은 스트라이크 판정을 받았으며, 빨간색 점은 볼 판정을 받았다. 이처럼 한 경기에서 기록된 야구공의 위치 데이터를 분석함으로써, 해당 경기의 스트라이크 존을 나타내는 직사각형 영역을 정의할 수 있게 된다.
<그림 H.1> - 한 경기에서 기록된 야구공의 2차원 평면에서의 위치 정보. 파란 점은 스트라이크, 빨간 점은 볼 판정을 받았다. 그림 생략.
여러분은 2차원 평면 상의 점으로 구성된 2개의 집합 P1, P2와 2개의 양의 정수 c1, c2를 입력받는다. R을 모든 변이 x축과 y축에 평행한 직사각형이라 하고, s를 P1 ∩ R에 속하는 점의 개수, b를 P2 ∩ R에 속하는 점의 개수로 정의하자. 이때 함수 eval(R) = c1 × s - c2 × b의 값이 최댓값이 되게 하는 직사각형 R을 찾는 프로그램을 작성하시오.
--------
[입력]
입력은 표준 입력을 사용한다.
입력의 첫 줄에는 P1에 속하는 점의 개수를 나타내는 정수 n1 (1 ≤ n1 ≤ 1,000)이 주어진다. 다음 n1개 줄에서는 P1에 속하는 점의 좌표를 나타내는 2개의 정수 x, y (-109 ≤ x, y ≤ 109)가 각각 주어진다. 각 점의 좌표는 (x, y)로 표현할 수 있다.
그 다음 줄에는 P2에 속하는 점의 개수를 나타내는 정수 n2 (1 ≤ n2 ≤ 1,000)가 주어진다. 다음 n2개 줄에서는 P2에 속하는 점의 좌표를 나타내는 2개의 정수 x, y (-109 ≤ x, y ≤ 109)가 각각 주어진다.
집합 P1 ∪ P2에 속하는 점에서 어떠한 두 점도 완전히 같은 좌표에 위치하지 않는다. 즉, 모든 점은 서로 다른 좌표에 위치함이 보장되어 있다.
입력의 마지막 줄에는 2개의 정수 c1, c2 (1 ≤ c1, c2 ≤ 10,000)가 주어진다.
--------
[출력]
출력은 표준 출력을 사용한다. 입력으로 주어진 P1, P2, c1, c2에 대해 eval(R)의 최댓값을 한 줄에 출력한다.