문제
좌표평면에 빨간색 점 N개와 파란색 점 M 개가 있다. 또한, 자연수 W, H가 주어진다.
i번째 (1 ≤ i ≤ N) 빨간색 점의 좌표는 (rxi, ryi)이고, j번째 (1 ≤ j ≤ M) 파란색 점의 좌표는 (bxj, byj)이다.
모든 점들의 좌표는 서로 다르다.
가로 W, 세로 H인 직사각형을 변이 좌표축에 평행하고 꼭짓점이 정수 좌표에 놓이도록 할 것이다.
이 때 직사각형이 포함하는 빨간색 점과 파란색 점의 개수의 차가 가장 크게 만들고 싶다.
직사각형이 점을 포함한다는 것은, 직사각형의 왼쪽 아래 꼭짓점 좌표가 (a, b)이고
점의 좌표가 (x, y)일 때 a ≤ x ≤ a + W, b ≤ y ≤ b + H를 만족한다는 것이다.
개수의 차의 최댓값을 구하고, 그 답에 해당하는 직사각형의 위치를 찾아라.
아래 예는 평면에 빨간색 점 3개와 파란색 점 4개가 있는 상황을 보여 준다.
원래 각 점에는 크기가 없지만 설명의 편의상 빨간색 점은 동그라미, 파란색 점은 세모로 표시하였다.
W = 5, H = 3으로 주어졌다고 하자.
그 경우 아래와 같이 직사각형의 왼쪽 아래 꼭짓점을 (3, 3)에 놓으면
포함하는 빨간색 점이 1개, 파란색 점이 3개가 되어 개수의 차가 2가 된다.
직사각형을 어디에 놓더라도 개수의 차를 3 이상으로 만들 수는 없기 때문에 답은 2가 된다.
입력
첫 번째 줄에 빨간색 점의 개수 N과 파란색 점의 개수 M, 직사각형의 가로 및 세로 길이 W와 H가 각각 주어진다.
그 다음 줄부터 N개의 줄에 걸쳐 각 빨간색 점의 x, y좌표 rxi, ryi가 주어진다.
그 다음 줄부터 M개의 줄에 걸쳐 각 파란색 점의 x, y좌표 rxj, ryj가 주어진다.
[제약 조건]
1 ≤ N, M ≤ 100,000
1 ≤ W, H ≤109
1 ≤ rxi, ryi ≤ 10<9 (1 ≤ i ≤ N)
1 ≤ bxj, byj ≤ 109 (1 ≤ j ≤ M)
출력
첫 번째 줄에 빨간색 점과 파란색 점의 개수의 차의 최댓값을 출력한다.
두 번째 줄에 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표를 출력한다. 답이 여러 개라면 아무 것이나 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 5점 | 1 ≤ N, M, W, H, rxi, ryi, bxj, byj < 50. |
| #2 | 11점 | 1 ≤ N, M, W, H, rxi, ryi, bxj, byj < 1,000. |
| #3 | 15점 | 1 ≤ N, M ≤ 100. |
| #4 | 9점 | 1 ≤ N, M ≤ 1,000. |
| #5 | 60점 | 추가 제약 조건 없음. |
예제1
3453
32
25
76
12
43
36
74
2
33
예제2
3344
11
22
33
13
31
44
2
-2-2