문제: 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'..
해법
2011. 6. 2. 18:39
공지사항
- Total
- 158,306
- Today
- 99
- Yesterday
- 87
링크
TAG
- Dijkstra
- vote
- Knuth Optimization
- ioi
- USACO
- IOI2014
- Tree
- z-trening
- moore
- BOI 2001
- idea
- optimization
- Algorithm
- IOI2011
- Splay Tree
- dynamic programming
- IOI2013
- Segment tree
- Parametric Search
- BOI
- majority
- Dynamic Pramming
- TRIE
- Boyer-Moore Majority Vote Algorithm
- IOI2012
- Divide & Conquer
- BOI 2009
- Greedy Method
- Boyer
- HackerRank