ALLBARN2 - All Possible Barns

no tags 

Farmer John is going to build a new rectangular barn. But the 4 corners of the barn mustn't be on soft soil. He examined the ground and found that there are only N (4 <= N <= 1,000) appropriate points for the corners. He wants to know the number of possible ways to build the new barn.

Given the points, help him find the answer.

Input:

Input exactly contains 10 test cases each of them as follows:

  • Line 1: A single integer, N.
  • Lines 2..N+1: Each line has two space-separated integers x, y which are the coordinates of a point. The magnitude of the coordinates is not more than 16,000. All points will be distinct.

Output:

For each Test case print one line contains:

  • Line 1: The number of possible ways to build the new barn.

Sample:

Input
8
1 2
1 -2
2 1
2 -1
-1 2
-1 -2
-2 1
-2 -1
[and 9 more Test cases ...]

Output
6
[and 9 more Test cases ...]
Output Details:

The possible answers are: {1, 2, 6, 5}, {1, 3, 6, 8}, {1, 4, 6, 7}, {2, 3, 5, 8}, {2, 4, 5, 7}, {3, 4, 8, 7}


hide comments
:D: 2012-11-14 19:05:14

Yes, that's a reoccurring problem on SPOJ. It's hard to set up a tight limit so that java would still pass.

I got a second time with a pretty crude O(N^2*log(N)), so definitively port it to C++, since it could be the best solution. That, of course, if it works and really is O(N^2) ;)

George K: 2012-09-13 07:51:36

I keep getting timeout with O(N^2) algorithm. Is it just Java being slow?

:D: 2012-08-28 12:41:34

Don't use exact judge unless it's really needed, like in some formatting problem. Even then I would recommend using dots '.' instead of spaces and still having a default judge. If you're just outputting numbers it's pointless.

Hussain Kara Fallah: 2012-08-28 02:24:57

NOTE:: The judge in this problem is exact judge so take care for printing endline or '\n' after each testcase and after the last case too :))))


Added by:Se7s
Date:2012-08-28
Time limit:1s-1.268s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Syrian Qualifications for IOI Round #5