問題
yukicoder Advent Calendar Contest 2022 B – Draw A Convex Polygon
スコア問題となっていますが、通常問題と同様に解くことができます。
解説
偏角が異なるベクトルを集めれば、偏角 ( $\text{atan2}(y,x)$ ) の降順に並べ替えることで凸包の輪郭をとることができます。一周を一度に作るかわりに、 $90$ 度または $45$ 度ぶん作り、適切に変換することにすると、ソートの比較関数に外積を直接用いることができます。
$0\leq x$ と $0\lt y$ として、偏角が相異なる、すなわち $x/y$ が異なるベクトルを、 $x+y$ の小さい順にたくさん取り出したいです。実際に $x+y$ が小さい順に $(x,y)$ を試し、 $\gcd (x,y)=1$ なら採用することにすれば、偏角が既約分数であることから得られるベクトルは偏角が相異なることが保証されます。
$0\leq x$ かつ $0\lt y$ の範囲でベクトルを $250\ 000$ 個集め、偏角でソートすると、これが凸包の $90$ 度ぶんになるので、適切に変換しながら $4$ 回繰り返すと $1\ 000\ 000$ 頂点の凸包の辺が得られます。あとはこの辺に沿って座標を移動させていけば、すべての頂点の座標が得られます。
最適性
頂点数が十分大きい $4$ の倍数のとき、座標の絶対値（ $\max{|x|,|y|}$）の最小化についてこの方法が最適であることを示します。
凸包を $4$ 方位（座標軸に平行な角度）で分割します。分割にちょうど重なる辺は均等に振り分けます。 $4$ つの部分は全く同じ構造をしています。今、 $1$ つの領域の辺の配置を決め、 $x$ と $y$ の値の幅を $X$ , $Y$ とすると、適切な回転によって $4$ つの領域を埋め、座標の幅が $X+Y$ の答えを作ることができます。一方、幅 $D$ の答えがあるとすれば、合計が $4D$ 以下であることから、どれか $1$ つの領域では幅の合計が $D$ 以下になります。よって $1$ つの領域における $X+Y$ の最小化が直接答えの最適化につながることになるので、 $x+y$ の小さい順に選ぶのが最適であることが示されました。
実装例
出力は $-75\ 574\ 918\leq x\leq 75\ 574\ 917,-75\ 574\ 918\leq y\leq 75\ 574\ 917$ を満たします。