CGL_4_A: Convex Hull
与えられた点を含む凸包(Convex Hull)を求める
最初に思いつくのは、どこかの点から始めてぐるっと外周を探していくというやり方
最初の点はたとえばy座標が最も小さい点にしておけばよさそう
でも単純にやると、次の点を求めるのにn-1個の点を調べる必要がありそうで
全体でO(n^2)になってしまう
次の頂点を調べる時に再利用できる計算結果があればいいんだけどあるかなあ
思いつかないなあ
三角形から初めてひとつずつ点を足しつつそれが外周上にあるか判定するっていう
やり方もありうるかな？
なかなかややこしそう
問題を見直す
- スタックとソートを使う
優先度キューとか使いそうなイメージだったけどそうでもない模様
- 外周を回るような矢印
外周を回りつつ求めるのかなあ
なぜか矢印がふたつ書かれている
始点はx座標が最小・最大のところ
これは意味ありげ
時計回りに書かれているのもちょっと気になるといえば気になる
解答は反時計回りに出力することになっているのに！
- データは最大10万個
2乗のオーダでは間に合いそうにない
- x座標、y座標は -10000から10000までの整数
整数であることを使うだろうか
xを-10000から10000まで変化させつつ、y座標が最大・最小の点を
見つけていけば外周の候補にはなる
y座標が最大・最小だからと言って外周に含まれるとは限らないから
数を絞ってからマジメに判定？
