CVXPOLY  Convex Polygons
English  Vietnamese 
You are given n points in the 2D 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
hide comments
Race with time:
20090414 12:17:32
Time limit has been updated. 

Ajay Somani:
20090414 12:17:32
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. 

[Trichromatic] XilinX:
20121109 11:19:23
Almost the same as problem BOYSCOUT  with a very strict time limit. 
Added by:  Race with time 
Date:  20090219 
Time limit:  1.913s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Code Craft 09 