　面の個数を $f$ とおく（最も外側の開いた面も含むことに注意せよ）と，オイラーの多面体定理より，
$$
n=10000-f+2
$$
が成り立つ．よって $f$ が最大であるときを考えればよい．各面は $3$ 辺以上持つため，次が成り立つ．
$$
3f \leqq 2 \cdot 10000
$$
よって $f$ の最大値は $6666$ であり，このとき $n = 3336$ となる．実際，次のように $3336$ 個の点をとって，各 $X_k$ と $A,B$ を結び，線分 $X_iX_{i+1}(i=1,2,...,3332)$ を結ぶとこで $10000$ 本の線分を引くことができる．
$$A(-1,0),~ B(1,0),~ X_{k}(0,k) \quad (k=1,2,...,3334)$$
以上より $n$ の最小値は $\mathbf{3336}$ である．
公式解説
https://onlinemathcontest.com/contests/omcb015/editorial/10781
凸包が $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$ と分かります．
凸包を使うやつ
https://onlinemathcontest.com/contests/omcb015/editorial/10781/565
　$n$ を $2$ 以上の正整数とします．平面上に相異なる $n$ 個の点をとり，**良い点**とします．相異なる $2$ つの良い点を結ぶ線分を，次が成り立つように $10000$ 本引くことができました．
- $10000$ 本の線分のうち，どの $2$ 本も端点を除いて共有点を持たない．

 $n$ としてありうる最小値を求めてください．