CVXPOLY - Convex Polygons
English | Vietnamese |
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.
Input
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.
Output
T lines each corresponding to the answer of corresponding test case.
Example
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
Constraints
Input Set 1 : numberOfTestCases <= 100, 3 <= n <= 10 timeLimit: 5 seconds Input Set 2 : numberOfTestCases <= 50, 3 <= n <= 100 timeLimit: 5 seconds
Added by: | Race with time |
Date: | 2009-02-19 |
Time limit: | 1.913s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Code Craft 09 |