4391 : Strike Zone
- 제한시간
- 1000 ms
- 메모리제한
- 512 MB
- 해결횟수
- 2 회
- 시도횟수
- 2 회
문제
The strike zone in baseball is the volume of space which a baseball must pass through in order to be called a strike, if the batter does not swing. A baseball that misses the strike zone is called a ball, if the batter does not swing. Figure H.1 shows the locations of baseballs at plate which were captured by a ball tracking device during a baseball match. Each blue point was called a strike and each red point was called a ball during the match. This may motivate us to define a rectangular region that represents the strike zone of the match, by analyzing such a ball tracking data of the match.

In this problem, you are given two sets, P1 and P2, of points in the plane and two positive constants c1 and c2. You are asked to find an axis-parallel rectangle R that maximizes the evaluation function eval(R) = c1 × s - c2 × b, where s is the number of points in P1 ∩ R and b is the number of points in P2 ∩ R.
입력형식
Your program is to read from standard input. The input starts with a line containing an integer n1 (1 ≤ n1 ≤ 1,000), where n1 denotes the number of points in P1. In the following n1 lines, each line consists of two integers, ranging -109 to 109, representing the coordinates of a point in P1. The next line contains an integer n2 (1 ≤ n2 ≤ 1,000), where n2 denotes the number of points in P2. In the following n2 lines, each line consists of two integers, ranging -109 to 109, representing the coordinates of a point in P2. There are no two points in P1 ∪ P2 that share the same x or y coordinate. Then the next line consists of two integers, c1 and c2, ranging 1 to 10,000.
출력형식
Your program is to write to standard output. Print exactly one line consisting of one integer that is eval(ܴR), where R is an axis-parallel rectangle with the maximum possible eval value for P1 and P2 with respect to c1 and c2.
입력 예복사하기 2 -1 -1 4 4 2 0 0 2 2 5 2 |
출력 예복사하기 6 |
입력 예복사하기 3 0 5 3 3 8 -1 3 1 4 6 0 7 1 3 2 |
출력 예복사하기 4 |