시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB | 356 | 119 | 64 | 33.684% |
좌표평면에 빨간색 점 $N$개와 파란색 점 $M$개가 있다. 또한, 자연수 $W$, $H$가 주어진다.
$i$번째 ($1 ≤ i ≤ N$) 빨간색 점의 좌표는 $(rx_i, ry_i)$이고, $j$번째 ($1 ≤ j ≤ M$) 파란색 점의 좌표는 ($bx_j , by_j)$이다. 모든 점들의 좌표는 서로 다르다.
가로 $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$좌표 $rx_i$, $ry_i$가 주어진다.
그 다음 줄부터 $M$개의 줄에 걸쳐 각 파란색 점의 $x$, $y$좌표 $bx_j$, $by_j$가 주어진다.
첫 번째 줄에 빨간색 점과 파란색 점의 개수의 차의 최댓값을 출력한다.
두 번째 줄에 직사각형의 왼쪽 아래 꼭짓점의 $x$, $y$좌표를 출력한다. 답이 여러 개라면 아무 것이나 출력한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 5 | $1 ≤ N, M, W, H, rx_i, ry_i, bx_j , by_j ≤ 50$. |
2 | 11 | $1 ≤ N, M, W, H, rx_i, ry_i, bx_j , by_j ≤ 1,000$. |
3 | 15 | $1 ≤ N, M ≤ 100$. |
4 | 9 | $1 ≤ N, M ≤ 1,000$. |
5 | 60 | 추가 제약 조건 없음. |
3 4 5 3 3 2 2 5 7 6 1 2 4 3 3 6 7 4
2 3 3
3 3 4 4 1 1 2 2 3 3 1 3 3 1 4 4
2 -2 -2
Olympiad > 한국정보올림피아드 > KOI 2022 2차대회 > 초등부 4번