今日解いた競プロの問題。

ABC215-F: 急に答えが見えたので解いた。まず、どんな2点でも「一方のX座標≦もう一方のX座標」が成り立つので、N個の各点について「X座標がその点のX座標以上となる点の中で距離最大の点」を求められれば良いことが分かる。

そのような点は、斜め45度の線とx軸方向の線を用いて4象限に分けられる。

Cを切片として、

• $y=x+C$の線より上側
• $y=x+C$より下側で$y=C$より上側
• $y=C$より下側で$y=-x+C$より上側
• $y=-x+C$より下側

これらの象限における距離最大の点は、$y=x+C$なる線や$y=-x+C$なる線を移動させていく平面走査法をすることでそれぞれ高速に求められる。ソートがボトルネックとなり$O(N\log N)$。

---

試作中のVRゲームに音が付いた。OpenALにおいて音声ファイルの読み込みをどうしようか悩んでいたが、vcpkgでfreealutを入れたらとりあえず.wavについては割と楽にできた。(al.hをAL/al.hに書き換える必要があるなどの問題はあったが…)

oggとかの読み込みが次点でやりやすそうな気がする。liboggとlibvorbis入れてごにょごにょするだけのはず。

開発が多少ひと段落したので今日は夕方以降作業を休んだ。連日同じプロジェクトのコードをいじっているので脳味噌が焼け付いている感触がある。

---

今日摂取したコンテンツ。

https://www.food-culture.jp/introduction/event/report01.html

メイラード反応・カラメル化反応に関する解説。実際の料理を例にとりながら説明していて分かりやすかった。