TopCoder SRM 585: EnclosingTriangleColorful

まず青い点、黄色い点、緑の点を結んた三角形について考える。

まず左側の黄色い点と右側の緑色の点を選択する。
このとき結んだ直線より下に黒点が存在する場合は、どの青い点を選んでも三角形の外側になるため、該当する三角形は存在しない。

そして２点を選択すると

• 左側の点から各黒点へ直線を伸ばした時の y = m の交点の最小 x 座標
• 右側の点から各黒点へ直線を伸ばした時の y = m の交点の最大 x 座標

が求まり、この間にある青い点を選ぶと全ての黒点が三角形の内側に収まる。

このように条件を満たす青黄緑の三角形の個数をO(n * m * m)で求めることができる。他の色の組み合わせの三角形の個数についても、座標を回転させることで同様に求められる。

public class EnclosingTriangleColorful {
    int det(int x1, int y1, int x2, int y2) {
        return x1 * y2 - x2 * y1;
    }

    public int getNumber(int m, int[] x, int[] y) {
        int n = x.Length;
        int ans = 0;
        for (int i = 0; i < 4; i++) {
            for (int y1 = 1; y1 < m; y1++) {
                for (int y2 = 1; y2 < m; y2++) {
                    int x1 = 0;
                    int x2 = m;
                    int lower = 1;
                    int upper = m -1;

                    for (int j = 0; j < n; j++) {
                        if (y1 < y[j]) {
                            int dy = y[j] - y1;
                            int dx = x[j] - x1;
                            int ry = m - y[j];
                            int crossX = x[j] + (int)Math.Floor(1.0 * ry * dx / dy);
                            upper = Math.Min(upper, crossX);
                        }
                        if (y2 < y[j]) {
                            int dy = y[j] - y2;
                            int dx = x[j] - x2;
                            int ry = m - y[j];
                            int crossX = x[j] + (int)Math.Ceiling(1.0 * ry * dx / dy);
                            lower = Math.Max(lower, crossX);
                        }
                        if (det(x2 - x1, y2 - y1, x[j] - x1, y[j] - y1) < 0) {
                            upper = -1;
                            lower = m + 1;
                            break;
                        }
                    }
                    ans += Math.Max(upper - lower + 1 , 0);
                }
            }
            // rotate
            for (int j = 0; j < n; j++) {
                int X = x[j];
                int Y = y[j];
                x[j] = Y;
                y[j] = m - X;
            }
        }
        return ans;
    }
}