On a 2D plane, there are N non-overlapping points. Consider a string which forms a large cycle and surrounds all of the N points. As we shorten the string, the cycle will become smaller and smaller. Since we have to surround all points, when the string can not be any shorter, the string will form a polygon, which is called the convex hull.
There is a simple way to find a convex hull of N points, which is the so call “gift wrapping algorithm.” We will show the steps as follows.
1. Consider the coordinates, and select the point with the smallest X. If there are multiple choices, select the one with the smallest Y. Let a point P denotes this point.
2. Set a vector D=(0,1), denote the “direction”.
3. For all the other points, find the point, Q, which forms the smallest angle, Θ, between direction D and direction PQ. Use a dot product D*PQ = |D||PQ|cosΘ, we can use the value of cosΘ to compare the angles of Θ for different Q. If there are more than one Qs form the same Θ, choose the one with the largest |PQ|.
4. Do step 3 continuously until the convex hull is closed (we reach the first point).
Hint: to get the square root, use the function:
double sqrt(double x)
in math.h
There will be multiple cases in the input.
The first line contains a positive integer T, T≦100, which denotes the number of cases.
For each case, the first line contains an integers N ,2≦N≦1000, which is the number of points on the plane. There are N lines following, and each line contains 2 integers X and Y, which are the coordinates of that point. All coordinates are between -10000 and 10000.
Values will be separated with spaces.
For each case, output a line containing one integer denoting the minimum number of points needed to form a convex hull to cover all points.