CVXPOLY - Convex Polygons
You are given n points in the 2-D cartesian coordinate system. You are to determine the number of convex polygons with 3 or more vertices which can be formed by choosing a subset of the given points. To make matters simple, the input obeys the following conditions:
(1) No 3 points in the input are collinear.
(2) No 2 points will have the same coordinates.
Since the result can be quite large, you are required to output ( result % 1234567 ) instead.
First line contains an integer T, the number of test cases. In each test case, first line contains n, the number of points in the corresponding test case, next n lines contain 2 space separated integers denoting the coordinate of ith point. Absolute value of the coordinates do not exceed 10000.
T lines each corresponding to the answer of corresponding test case.
Input: 2 4 0 0 2 0 2 2 0 2 6 0 0 2 0 2 2 0 2 1 -1 1 3 Output: 5 42
Input Set 1 : numberOfTestCases <= 100, 3 <= n <= 10 timeLimit: 5 seconds Input Set 2 : numberOfTestCases <= 50, 3 <= n <= 100 timeLimit: 5 seconds
Race with time:
Time limit has been updated.
It seems the problem author has taken the time limit from the original solution and released test data. But the judge server at codecraft was faster than the judging machines at SPOJ, hence the strict time limit.
Almost the same as problem BOYSCOUT - with a very strict time limit.