空間凸包

以前O(n log n)の空間凸包を組もうとして挫折してずっと放置してたが、こないだの冬コンテストで出たのでそこそこ高速で楽な実装を考えてみた。
とりあえず、４点が同じ平面上に乗ってるのはないとして、
1. 点を徐々に追加していく
2. 凸包の各面が見えるか判定
3. 見える面を取り除き、見える面と見えない面の境界と追加する点を結ぶ面を新たに追加
っていうのをやるとO(n^2)になる。

見える面と見えない面の境界を探すのに、以前は面の隣接関係を保持してたけど、そうすると新たに追加したときに隣接関係修正するのとかが意外とめんどくさい。
よく考えたら、辺i->jをこの向きに含むような面は一つしかないので、O(n^2)でいいならてきとーに二次元配列に記憶しておけばよくて、面abcに対しては、辺ba,cb,acを含むような面を調べれば良い。
こんな感じで実装してみたらまともなコード長になったのでこれならICPCでも使えそう。

int[][] vs = new int[n][n]; //vs[i][j]=辺i->jをこの向きに含む三角形が、まだ調べてない:0、残った:-1、取り除かれた:1
List<int[]> crt = new ArrayList<int[]>();
crt.add(new int[]{0, 1, 2});
crt.add(new int[]{2, 1, 0});
for (int i = 3; i < n; i++) {
	List<int[]> next = new ArrayList<int[]>();
	for (int[] t : crt) {
		int v = ps[t[1]].sub(ps[t[0]]).det(ps[t[2]].sub(ps[t[0]])).dot(ps[i].sub(ps[t[0]])) < 0 ? -1 : 1;
		if (v < 0) next.add(t);
		for (int j = 0; j < 3; j++) {
			if (vs[t[(j + 1) % 3]][t[j]] == 0) {
				vs[t[j]][t[(j + 1) % 3]] = v;
			} else {
				if (vs[t[(j + 1) % 3]][t[j]] != v) {
					if (v > 0) next.add(new int[]{t[j], t[(j + 1) % 3], i});
					else next.add(new int[]{t[(j + 1) % 3], t[j], i});
				}
				vs[t[(j + 1) % 3]][t[j]] = 0;
			}
		}
	}
	crt = next;
}

ちなみに、見えるかどうかの判定を衝突グラフを作って行い、点の追加をランダム順にすると期待値的にO(n log n)になるらしい。
点pから面abcが見えて面dbaが見えない時、新たに面pabができ、面abcが取り除かれる。
この時、面dbaから見える点の集合は変化せず、面pabから見える点は面abcもしくは面dbaのどちらかから見えるのでこれらだけを調べれば良い。
(計算量の解析の部分ちゃんと理解してないので、ほんとにコレだけでいいのかは知らない)
実はO(n log n)のもがんばれば意外と短く出来るのかなー？？