static Point[] convexHull2D(Point[] ps, Point normal) {
        final Point dir = perpendicular(normal);  // 任意の点が相異ならdir=ps[1]-ps[0]でよい
        Arrays.sort(ps, new Comparator<Point>() {

            @Override
            public int compare(Point o1, Point o2) {
                double d = dir.dot(o2.subtract(o1));
                return !approxEquals(d, 0) ? (int) Math.signum(d) : 0;
            }
        });

        int n = ps.length;
        Point[] hull = new Point[2 * n];
        int k = 0; // k == hull.size()
        // 下側凸包（向き的に上側凸包というべきかも）
        for (int i = 0; i < n; hull[k++] = ps[i++]) {
            while (k >= 2 && ccw(hull[k - 2], hull[k - 1], ps[i], normal) <= 0)
                --k;  // 最後のベクトルから見て候補点が右側にあるなら、最後の点をはずす
            // 現状ccwが+2を返さないので縮退してると死ぬかもしれない
        }
        // 下側凸包の後に上側を加える
        int lowerEnd = k;
        for (int i = n - 2; i >= 0; hull[k++] = ps[i--]) {
            while (k > lowerEnd && ccw(hull[k - 2], hull[k - 1], ps[i], normal) <= 0)
                --k;
        }
        Point[] ret = new Point[k - 1];
        System.arraycopy(hull, 0, ret, 0, k - 1);  // 最後は重複しているので消す
        return ret;
    }