TopCoder SRM 585: EnclosingTriangleColorful
まず青い点、黄色い点、緑の点を結んた三角形について考える。
まず左側の黄色い点と右側の緑色の点を選択する。
このとき結んだ直線より下に黒点が存在する場合は、どの青い点を選んでも三角形の外側になるため、該当する三角形は存在しない。
そして2点を選択すると
- 左側の点から各黒点へ直線を伸ばした時の 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; } }