解説 ドロネー三角形分割を逐次添加 - 辺フリップ法で行う. 計算量 O(n^2) (各点について O(n) でそれを含む三角形を得,平均 O(log n) で更新.これを n 回行う). 使い方 double deaunay(vector<point> &P) 点集合 P を与え,ドロネー三角形分割する.E がドロネーグラフを表現する. TODO コード長の短縮とか,ひどい #define をなんとかするとか. 三角形分割木を構成すれば計算量が O(n log n) になるはずだが. ソースコード bool incircle(point a, point b, point c, point p) { a -= p; b -= p; c -= p; return norm(a) * cross(b, c) + norm(b) * cross(c, a) + norm(c) * cross(