ALLBARN2 - All Possible Barns
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.
|
|
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 |