UVa 10790

From Algorithmist
Jump to navigation Jump to search

10790 - How Many Points of Intersection?[edit]

Summary[edit]

There are points in the first row, and 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[edit]

There are ways to choose two points from the first row (order doesn't matter), and 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:

Implementations[edit]

Input[edit]

2 2
2 3
3 3
20000 20000
0 0

Output[edit]

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