提示: 欢迎访问OurACM平台。
Problem 2153 A simple geometric problems

Accept: 43    Submit: 172
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

在一个平面图上,有N个不同的点,请问你最多能选取多少个点组成一个凸多边形。

Input

输入第一行为一个正整数T(1<= T < =100),表示有T组数据。

每组数据第一行为一个正整数N(3<= N <=50) 表示有N个点。

接下来N行,每行两个整数xi,yi,表示第i点的坐标。

保证任意3个点不共线。

Output

对于每个询问,先输出“Case#i: ”,i表示第i组数据,接着输出一个整数,表示最多能选取的点数。

Sample Input

1 9 10 8 3 9 2 8 2 3 9 2 9 10 10 3 8 10 0 0

Sample Output

Case#1: 8

Submit  Back  Status  Discuss