ICPC 2019 Asia Regional –Seoul Problem H- Strike Zone > 문제은행 : 정보올림피아드&알고리즘

공지   새로운 정올 베타버전이 공개되었습니다.    자세히보기


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


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP