PS 이야기

문제: 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'..

문제: http://www.csc.kth.se/contest/boi/subway.pdf 해법: http://www.csc.kth.se/contest/boi/subway-spoiler.pdf 이 문제에 대한 증명을 하지는 못 하겠다... 그냥 느낌으로 올 뿐이지 증명이 가능한지는... 잘 모르겠다... ㅠㅠ 예제 2번 데이터를 통하여, 방법을 설명하겠다. 1. 우선 처음에 입력 받을 때 방향에 상관없이 입력받고, 오름차순 정렬을 한다. 9 15 33 33 41 81 97 100 2. 홀수번째와 짝수번째의 방향을 다르게 한다. 9R 15L 33R 33L 41R 81L 97R 100L 3. 다음에 subway의 rail을 일직선에 나타내고 그에 따라 x좌표를 대입한뒤 정렬하면, 9 (200-15) 33 (20..