UVa 10790

10790 - How Many Points of Intersection?

• http://acm.uva.es/p/v107/10790.html

Summary

There are a points in the first row, and b points in the second one. Every pair of points from different rows is connected by a line segment. No three line segments have a common point of intersection. How many points of intersection (excluding endpoints) will there be?

Explanation

There are ${a \choose 2}$ ways to choose two points from the first row (order doesn't matter), and ${b \choose 2}$ ways to choose two points from the second row.

Every choice of two points from the first row and two points from the second row corresponds to exactly one point of intersection (namely, the intersection of diagonals of the convex quadrilateral built on them). And conversly, each point of intersection corresponds to two pairs of points from first row and second row respectively (namely, the endpoints of intersecting segments).

Hence, we have a bijection, and the total number of points of intersection is:

${a \choose 2}{b \choose 2} = {ab(a-1)(b-1) \over 4}$

Input

2 2
2 3
3 3
20000 20000
0 0

Output

Case 1: 1
Case 2: 3
Case 3: 9
Case 4: 39996000100000000