2017-10-29 07:41

Infinity Point Sets

  • as
  • numbers
  • it
  • lines
  • each

Problem Description
This story comes from an ancient book written by an old frog philosopher.

When will be the end of the world? Perhaps the best way to understand is using geometry for a calculation.

At first, you should draw some points on a piece of paper. Each time you should choose two points and connect them with a segment. When there are two segments meet and produce a new point at the cross, you add that point to the paper, and try to connect it with previous ones as before.

You should do this again and again, keep drawing segments, and adding points if possible, until there are no new segments to draw. Then is the end of the world, the old frogs will die and a new age will begin.

As you can see, different sets of initial points lead to different results. For some sets of points, the end of the world will never come, we call those sets Infinity.

Now you are given N points, and you need to find, among all the possible subsets of those N points not including empty set, so there will be 2N−1 sets in total), how many of them are not Infinity?

First line contains an integer T, which indicates the number of test cases.

Every test case begins with an integers N, which indicates the numbers of points.

In the following N lines, the ith line contains two intergers xi and yi, indicating the coordinate of ith point is (xi,yi).

⋅ 1≤T≤10.

⋅ for 90% data, 1≤N≤100.

⋅ for 100% data, 1≤N≤1000.

⋅ 1≤xi,yi≤104.

⋅ there is no a pair of points with the same coordinate.

For every test case, you should output `"Case #x: y", where x indicates the case number and counts from 1 and y is the result.

Because y could be very large, just mod it with 109+7.

Sample Input
0 0
0 2
2 2
2 0
0 0
0 2
2 2
2 0
1 2

Sample Output
Case #1: 15
Case #2: 30

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享