TopCoder SRM 568 - 1000: DisjointSemicircles

Problem Statement

给出2n个点，坐标分别为(i,0)(0 <= i < 2n)
有一些点对之间已经有连边
现在要给剩下的点配对
求是否存在一种方案，以配对的点为直径画n个半圆，使得所有半圆两两不交
1 <= 2n <= 50

Consider 2N points in a plane: (0, 0), (1, 0), ..., (2N - 1, 0). You want to label these points with integers, such that each integer in { 0, 1, ..., N - 1 } is used twice, and you can draw N disjoint semicircles in the plane, as follows: For each j, one of the semicircles has to connect the two points labelled j (See the image in Example 0).

Some points are already labelled. You are given a int[] labels consisting of 2N elements. If labels[i] is -1, it means that the point (i, 0) is not labelled yet, otherwise the point (i, 0) is labelled with the integer labels[i]. Each integer in { 0, 1, ..., N - 1 } will appear in labels either zero or two times.

Return the String "POSSIBLE" if the labelling is possible, "IMPOSSIBLE" otherwise.

Definition

Class DisjointSemicircles
Method getPossibility
Parameters vector<int>
Returns string
Method signature string getPossibility(vector<int> labels)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

Constraints

labels will contain between 2 and 50 elements, inclusive.
labels will contain an even number of elements.
Each element in labels will be between -1 and N - 1, inclusive, where 2N is the number of elements in labels.
Each integer between 0 and N - 1 will appear in labels either zero or two times.

Test cases

input
- labels { -1, 0, -1, -1, 0, -1 }
output
Returns "POSSIBLE"

note

If you label the points as { 1, 0, 1, 2, 0, 2 }, you can draw 3 disjoint semicircles as in the picture.
input
- labels { 1, -1, 2, 1, -1, 2 }
output
Returns "IMPOSSIBLE"

note

The labelling must be { 1, 0, 2, 1, 0, 2 }, but then you cannot draw 3 disjoint semicircles.
input
- labels { 2, -1, -1, 0, -1, -1, 2, 0 }
output
Returns "POSSIBLE"

note

The picture shows one of the possible ways of labelling and connecting.
input
- labels { -1, 1, 3, -1, 1, 3, -1, -1 }
output
Returns "IMPOSSIBLE"
input
- labels { -1, 5, -1, -1, 3, 6, 8, -1, 10, 7, -1, 7, 8, 0, 11, -1, -1, 11, 0, 10, 4, -1, 6, 5, -1, -1, 9, 9, 4, 3 }
output
Returns "POSSIBLE"
input
- labels { 4, -1, 2, 4, -1, 3, 3, 12, 2, 5, -1, 0, 9, 9, 8, -1, 12, 8, -1, 6, 0, -1, -1, -1, 5, 6, 10, -1, -1, 10 }
output
Returns "IMPOSSIBLE"
input
- labels { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }
output
Returns "POSSIBLE"

back to the menu

SRM 568 1 1000 DisjointSemicircles

Problem Statement

Definition

Limits

Constraints

Test cases