- 45度回転させる式は、X=x-y; Y=x+y
- （回転と同時にかかっている√2の倍率は無視します）
回転前のマンハッタン距離 = 回転後のチェビシェフ距離（座標の差の最大値）
- これで反時計回りに45度回転し、XY座標で2次元累積和を使うと解ける問題がある
- 例：ABC018 C – 菱型カウント
- 図示した
問題「菱型カウント」について詳しく
- （想定解は違うようです）
- 500x500の領域に○✕が書かれていて、ひし形を置けるスペースがいくつあるかという問題
- ひし形の定義がマンハッタン距離で与えられているが、事前計算でうまくやれそうにない
- 45度回転すると「空いてるか？」の判定が正方形領域になるので二次元累積和を使うとひし形の中央ごとにO(1)で判定できる
- （マンハッタン距離の問題は45度回転するとx,yを分離して考えられる、などと言われている）
Q マンハッタンならまず回転？
- A いいえ、medianなど色々ある。飛びつくのはやめましょう
- 例 070 - Plant Planning（★4）
類題（45度回転で解ける）
- ABC-E-Dist Max
