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).
(a) A set of chords.
(c) vetrices on the circle (d) M(i, j), i < j
(b) Maximum planar
subset of chords.
M(i, j): number of chords
in the maximum planar
subset (shaded region)
Figure 1: Maximum planar subset.
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.
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
0 4 0 4
1 9 5 7
2 6 8 11
The executable binary must be named as “mps” and use the following command format.
The Codes Hive believes in helping students to write clean codes that are simple to read and easy to execute.Based in New York, United States, we provide assignment help, homework help, online tutoring and project help in programming to the students and professionals across the globe.
Disclaimer: The reference papers/tutorials provided are to be considered as model papers only and are not to submitted as it is. These papers are intended to be used for research and reference purposes only.