1. 문제 링크 https://www.acmicpc.net/problem/15463
15463번: Blocked Billboard
The first line of input contains four space-separated integers: $x_1$ $y_1$ $x_2$ $y_2$, where $(x_1, y_1)$ and $(x_2, y_2)$ are the coordinates of the lower-left and upper-right corners of the first billboard in Bessie's 2D field of view. The next line co
www.acmicpc.net
2. 문제
3. 문제 요약
트럭이 두개의 광고판을 가리고 있을 때, 보이는 광고판의 총 면적을 구하여라.
4. 문제 입력
1. 광고판과 트럭은 모두 직사각형이다.
2. 3개의 줄에 각각 광고판1, 광고판2, 트럭의 좌표를 나타낸다.
3. 각 줄은 4개의 정수, ( x1 y1 x2 y2 )의 형태로 주어진다.
* 좌측하단 ( x1 y1 ), 우측상단( x2, y2 )
** 두 광고판은 서로 겹치지 않는다.
4. x, y 좌표의 범위는 [ -10³, 10³ ] 범위의 정수이다.
5. 문제 풀이
(1) Divide
처음에는 하나의 트럭과 두개의 광고판을 동시에 해결하면서 정답을 구하려했었다.
다만, 한번에 면적을 구하려고 하다보니, Board1, Board2의 위치와, 트럭의 경계좌표를 고려하는 과정에서
여러가지 경우를 고려해야 하는 점이 불편했다.
그러다 두 광고판끼리는 서로 독립적이니, 트럭과의 관계만 살펴보기로 했다.
1. Area1 = ( Board1 의 면적 - 트럭과 겹쳐진 면적 )
2. Area2 = ( Board2 의 면적 - 트럭과 겹쳐진 면적 )
작은 문제로 놓고 보니, 고려해야할 요소도 간단해지고,
동일한 방식으로 두 개의 면적을 구한다면, 코드도 깔끔하게 작성할 수 있을 것 같았다.
(2) 면적 구하기
( Board 의 면적 - 트럭과 겹쳐진 면적 )
= ( Board 1의 면적 ) + ( 트럭과 겹쳐진 면적 )
= ( Board 1의 면적 ) + ( 트럭과 겹쳐진 가로 ) * ( 트럭과 겹쳐진 세로 )
으로 다시 나누었다.
W = ( 트럭과 겹쳐진 가로 )
= Math.min( 트럭의 우측 끝, Board의 우측 끝 ) - Math.max( 트럭의 좌측 끝, Board의 좌측 끝 )
H = ( 트럭과 겹쳐진 세로 )
= Math.min( 트럭의 상단 끝, Board의 상단 끝 ) - Math.max( 트럭의 하단 끝, Board의 하단 끝 )
트럭의 우측끝이 Board의 좌측보다 왼쪽에 있거나, Board의 우측끝이 트럭의 좌측보다 왼쪽에 있는 것처럼
겹쳐지지 않은 상황에서는 값이 음수로 나오게 될 것이고,
어떤 모양으로 겹쳐져있는지 고려하지 않더라도, 복잡한 경우의 수들을 간단히 정리할 수 있다.
따라서, 트럭과 Board가 겹쳐진 경우( W>0 && H>0 )를 Board의 면적 - (W*H)를 이용하면 해결 된다.
6. 풀이 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int ans = 0;
int[][] loc = new int[3][4];
for (int i = 0; i < 3; i++) {
StringTokenizer stk = new StringTokenizer(br.readLine());
for (int j = 0; j < 4; j++)
loc[i][j] = Integer.parseInt(stk.nextToken());
}
for (int i = 0; i < 2; i++) {
ans += (loc[i][2] - loc[i][0]) * (loc[i][3] - loc[i][1]);
if (W > 0 && H > 0) ans -= (W * H);
}
System.out.println(ans);
Colored by Color Scripter
|