TopCoder SRM 566 - 1000: FencingPenguins

Problem Statement

平面上有中心在原点，一个点在(r,0)处的正n边形的n个顶点。

平面上还有m个企鹅，每个企鹅有一个位置和一个颜色，

现在要连一些边，使得每个点的度数都是0或2，

这样会构成若干个顶点不相交的圈，求满足以下条件的连边方案数：

1、每个圈里有至少一个企鹅；

2、任意两个圈不相交；

3、每种颜色的企鹅在同一个有限区域中；

4、每个企鹅在一个有限区域内；

n<=222,m<=50,r<=10^5,

企鹅的颜色保证是大写字母或者小写字母，

坐标范围<=10^5,企鹅离任一条n个点连的边的距离>10^-6

Paco collects penguins. His penguins like to play and run around on the ice where he lives. In order to keep his penguins safe he decided to construct fences to keep danger out.

Paco's penguins have fallen asleep. Acting quickly Paco placed numPosts posts in a circular configuration on the ice. Each post is placed radius meters from location (0,0). The posts are equally spaced with the first post being placed at location (radius, 0).

To construct the fencing, Paco will connect some pairs of fence posts using straight fences. No two segments of the fence are allowed to cross. In the resulting fencing, each fence post will either be unused, or it will be connected to exactly two other fence posts. The fences will create some enclosed areas. In order to avoid wasting resources, Paco requires that each of the enclosed areas has to contain at least one penguin.

Paco's penguins come in many different colors. Penguins of the same color often like to play together. As a result, Paco would like to keep all penguins of the same color in the same enclosure. Two penguins are considered in the same enclosure if they can walk to each other without crossing some fence.

Paco would like to keep all his penguins safe so he would also like to guarantee that each penguin is in some enclosure.

You are given two ints numPosts and radius. You are also given two int[]s x and y representing the (x,y) location of each of the sleeping penguins. Each penguin is small enough to be considered a point. You are also given a String color. The i-th character of color is an uppercase or lowercase alphabetic character representing the color of the i-th penguin. Compute and return the number of fencings that Paco can use to keep his penguins safe. If it is not possible to create any enclosure that meets all the requirements return 0. Two fencings are considered different if two posts are connected in one fencing but not in the other. As the number of fencings can be quite large, please return the result modulo 100,007.

Test cases

input
- numPosts 4
- radius 10
- x { 2 }
- y { 1 }
- color "R"
output
Returns 3

note

If the posts are numbered starting from 0 at (radius, 0) and increasing in the counter-clockwise direction. The 3 resulting answers would be:

{(0,1,2)}
{(0,1,3)}
{(0,1,2,3)}
input
- numPosts 4
- radius 10
- x { 2, -2 }
- y { 1, -1 }
- color "RR"
output
Returns 1

note

The only way to satisfy all the requirements is to connect all the fence posts.

{(0,1,2,3)}
input
- numPosts 8
- radius 10
- x { 8, -8, -8, 8 }
- y { 1, -1, 1, -1 }
- color "BBBB"
output
Returns 25

note

There are 25 ways to form a single fence around the penguins.
input
- numPosts 8
- radius 10
- x { 8, -8, -8, 8 }
- y { 1, -1, 1, -1 }
- color "RGBY"
output
Returns 50
input
- numPosts 6
- radius 5
- x { 0, 0 }
- y { -4, 4 }
- color "rB"
output
Returns 6

note

There are the six possible ways to fence these two penguins:

{(0,1,2,3,4,5)}
{(0,1,2,4,5)}
{(1,2,3,4,5)}
{(1,2,4,5)}
{(1,2,3),(0,4,5)}
{(0,1,2),(3,4,5)}
input
- numPosts 3
- radius 5
- x { 4 }
- y { 3 }
- color "y"
output
Returns 0
input
- numPosts 200
- radius 100000
- x { 1020, 30203, 2302, 203, -12321, -21332, 8823, -2133, 2323 }
- y { -123, 2131, 4434, 1223, 43434, 2323, 4343, -213, -2325 }
- color "YBYBWWBRr"
output
Returns 27547

back to the menu

SRM 566 1 1000 FencingPenguins

Problem Statement

Definition

Limits

Notes

Constraints

Test cases