2369. Circle Artwork

单点时限: 2.0 sec

内存限制: 256 MB

Circle is an ancient and universal symbol of unity, wholeness, infinity, the goddess, and female power. It is referenced frequently in religion and art. In this problem, we act as a modern artist and would like to draw our painting with points and circles, and clearly colors should be used. First, we put some colored points on the canvas. The goal is to draw a circle for each color Ci, such that every colored point inside or on the boundary of that circle has color Ci. Also, each such circle should have at least two points on its boundary. Note that for some colors, it might be impossible to draw such a circle. In this problem, given a set of colored points, your task is to compute the largest number of colors for which there exists a circle conforming to the above conditions.

输入格式

There are multiple test cases in the input. For each test case, in the first line there is a positive integer n (1 ≤ n ≤ 100), which is the number of colored points. This is followed by n lines of the form Ci Xi Yi where Ci is the color of the ith point and Xi Yi specify its coordinates. Each color string is made up of at most 20 small English letters. Coordinates are integers between -1,000,000 and 1,000,000. The last line of each test case contains a single 0.

输出格式

For each test case, write a single line which contains the largest number of colors for which there exists a circle conforming to the above conditions.

样例

Input
4
red 1 1
blue 1 2
blue 3 2
yellow 3 3
0
Output
1

0 人解决,2 人已尝试。

0 份提交通过,共有 6 份提交。

9.9 EMB 奖励。

创建: 11 年,10 月前.

修改: 2 年,11 月前.

最后提交: 8 年,10 月前.

来源: Tehran 2007-2008

题目标签