[Problem proposal] All Farthest Neighbors in Convex Polygons

[tatyam-prime]

Problem name: All Farthest Neighbors in Convex Polygons

Problem

$xy$ 平面に $N$ 個の点 $(x_0, y_0), \dots, (x_{N-1}, y_{N-1})$ があり, これらは反時計回りに (狭義) 凸多角形を成します.
$\text{ans}_i := {\arg\max}_{j=0}^{N-1}\sqrt{|x_j - x_i|^2 + |y_j - y_i|^2}$ と定義します．
$\text{ans}_0, \dots, \text{ans}_{N-1}$ を求めてください．

Constraint

• $3 \le N \le 5 \times 10^5$ とか？

Solution / Reference

• SMAWK algorithm
  • Geometric applications of a matrix searching algorithm
  • https://codeforces.com/blog/entry/110844
• monotone minima

Input

N
x_0 y_0
: 
x_{N-1} y_{N-1}

Output

ans_0
: 
ans_{N-1}

Note / Disucussion

• SMAWK algorithm がなさそうだったので
• テストケース作成は難しそう

[maspypy]

ありがとうございます。

「テストケース作成は難しそう」というのはどういうことですか？
Library Checker はコンテストサイトではないので、恣意的な嘘解法が通ることはそんなに問題ではないです。
単にこの頂点数の凸多角形を作るのが大変ということですか？

[tatyam-prime]

嘘解法を落とすのが大変だったという https://jag-icpc.org/?plugin=attach&refer=2023%2FPractice%2F%E5%A4%8F%E5%90%88%E5%AE%BF%2F%E8%AC%9B%E8%A9%95&openfile=G.pdf の記憶だったんですが，実際はこれより単純な問題なのでそんなに大変じゃなさそうという気になってきました

[tatyam-prime]

複数ある場合, 最小の index にするのか, どれでも良いとするのかは議論点かな

[tatyam-prime]

自然な実装として, SMAWK に $N \times 2N$ 行列を与えて, SMAWK は最小の index を返すというのが考えられますが, それは「頂点 $i$ から反時計回りに見て最初にくる最遠点」になりますね

[maspypy]

最小インデックスだと、反時計回り順で最寄りというわけではないのか。
最大距離のひとつ、としてしまうのがみんなにとって楽な気はします。

ちょうど最近
https://judge.yosupo.jp/problem/furthest_pair
が作られたので、gen は使いまわせるかもしれません。

[maspypy]

これで良さそうです。