Problem: Maximum Planar Subset
Given is a set C of n chords of a circle (see Figure 1 (a)). We assume that no two chords of C share an endpoint.
Number the endpoints of these chords from 0 to 2n − 1, clockwise around the circle (see Figure 1 (c)). Let
M(i, j), i ≤ j, denote the number of chords in the maximum planar subset (i.e., no two chords overlap each
other in the subset) in the region formed by the chord ij and the arc between the endpoints i and j (see
Figure 1 (d)). As the example shown in Figure 1 (a), M(2, 7) = 1, M(3, 3) = 0, and M(0, 11) = 3. You are
asked to write a program that computes the number of chords in the maximum planar subset in a circle of n
chords, i.e., compute M(0, 2n − 1), and reports the details of each chords, as shown in Figure 1 (b).
0
2n−2 1
2
0
1
2
3
4
5 6
7
8
9
10
11
a
b
c
e
d
f
0
1
2
3
4
5 6
7
8
9
10
11
c f
b
i
j
(a) A set of chords.
(c) vetrices on the circle (d) M(i, j), i < j
2N−1
(b) Maximum planar
subset of chords.
M(i, j): number of chords
in the maximum planar
subset (shaded region)
Figure 1: Maximum planar subset.
Input
The input consists of an integer 2n, 1 ≤ n ≤ 20, 000, denoting the number of vertices on a circle, followed by
n lines, each containing two integers a and b (0 ≤ a, b ≤ 2n − 1), denoting two endpoints of a chord. A single
“0” (zero) in the input line signifies the end of input.
Output
The output file reports the number of chords in the maximum planar subset in the input circle of n chords,
followed by a list of the two endpoints for each resulting chord in the maximum planar subset (sorted by the
first endpoint in the increasing order).
Here is an input/output example (see Figure 1):
Sample Input Sample Output
12 3
0 4 0 4
1 9 5 7
2 6 8 11
3 10
5 7
8 11
0
Command-line Parameter:
The executable binary must be named as “mps” and use the following command format.
./mps
