OMCB015(G) - 凸包を使うやつ

凸包が $k$ 点からなるとします． $n$ 点のうちある $3$ 点が存在してそれらが共線となるような場合は明らかに無駄なので無視します．(これにより， $n$ が十分大きい時 $k \geq 3$ に注意)

三角形分割した後の内角の総和を考えます．

凸包を構成する頂点は全部合わせて $k$ 角形の内角の総和，すなわち $180k-360$ 度集まり，それ以外の頂点にはそれぞれ $360$ 度集まるので，合計すると $360(n-k)+180k-360=360n-360-180k$ 度となります．

すなわち，三角形は $2n-2-k$ 個集まります．

三角形の辺は，凸包の辺以外はダブルカウントされ，凸包の辺は一回だけカウントされることから，辺の数は $3n-3-k$ 本引かれ，これが $10000$ 以上となる最小の $n$ は $3336$ と分かります．