티스토리 뷰

해법

[z-trening] z-dots

전명우 2011.06.02 18:39
문제: http://z-trening.com/tasks.php?show_task=5000000140

우선 한 점 p에 대해서 d(p) 값을 구하는 과정에 대해서 알아보자.

문제에서 max(|Ax-Bx|,|Ay-By|) 부분 때문에 점 a에 다음과 같이 두 대각선을 귿고 4개의 사분면으로 나누었다.

우선 점 p(빨간점)을 원점으로 보도록 대칭이동 시키자.

'+y' 라고 쓴 사분면 안에 있는 점 q에 대해서 답에 qy 가 더해짐을 의미하고
'-x' 라고 쓴 사분면 안에 있는 점 r에 대해서 답에 -rx 가 더해짐을 의미한다.
'-y', '+x' 도 마찬가지이다.


그러면 각 사분면에 대해서 +y, +x, -y, -x 의 값만 더하려면 어떻게 해야하나?

영역 a는 '-x', '+y' 사분면을 영역 b는 '+y','+x' 사분면, 영역 c는 '+x','-y' 사분면, 영역 d는 '-y','-x' 사분면에 점들을 가지고 있다고 하자.
영역 a와 영역 b의 영향을 받는 '+y' 사분면에 대해서 V(a)+V(b) = +y,
영역 b와 영역 c의 영향을 받는 '+x' 사분면에 대해서 V(b)+V(c) = +x,
영역 c와 영역 d의 영향을 받는 '-y' 사분면에 대해서 V(c)+V(d) = -y,
영역 d와 영역 a의 영향을 받는 '-x' 사분면에 대해서 V(d)+V(a) = -x.

위의 4개의 방정식에 대한 연립방정식을 풀면,
V(a) = -x, V(b) = +x+y, V(c) = -y, V(d) = 0
따라서 a영역에 있는 점들에 대해서는 그 점들의 -x좌표값들의 합만 가지고 있으면 되고 b영역에 있는 점들에 대해서는 점들의 +x좌표+y좌표값들의 합, c 영역은 그 점들의 -y좌표값들의 합, d영역은 필요 없음을 알 수 있다.

따라서 a영역의 합 값과 b영역의 합 값, c영역의 합 값을 다 더하면 우리가 구하려는 답이 나옴을 알 수 있다.

그런데 예외처리를 해줘야할 부분이 있다. 바로 점 p에서 그은 대각선 위에 있는 점들에 대해서인데,

1번 점은 '+y' 사분면에 있다고 계산된다. 즉, 1번 점은 답에 +y좌표값이 더해진단 뜻이다.
※ 1번 점은 영역 a,b,d에 속해 있는데, V(a)에 의해서 -x, V(b)에 의해서 +x+y, V(d)에 의해서 0. 합하면 -x+x+y = y 만큼이 답에 더해진다.
3번 점은 '+x' 사분면에 있다고 계산된다.
그러나 4번 점은 '-x' 사분면과 '-y' 사분면에 있다고 2번 중복되서 계산된다.
반면에 2번 점은 계산이 되질 않는다.
그래서 4번 점 위치에 있는 점들에 대해서는 계산된 값에서 빼주고, 2번 점 위치에 있는 점들에 대해서는 계산된 값에서 더해준다.

 

신고

'해법' 카테고리의 다른 글

[USACO 2011 February Gold] The Lost Cows  (0) 2011.06.04
[USACO 2008 November Gold] Toys  (0) 2011.06.04
[z-trening] z-dots  (0) 2011.06.02
[BOI 2009] Monument  (0) 2011.05.22
[BOI 2009] Subway Signalling Error  (0) 2011.05.22
[BOI 2009] Candy Machine  (0) 2011.05.22
댓글
댓글쓰기 폼