Count the squaresProblem code: D6 |
All submissions for this problem are available.
Everyone knows what a square looks like. Mathematically, a square is a regular quadrilateral. This means that it has four equal sides and four equal angles (90 degree angles).
One beautiful day, Johnny eagerly examined the interesting properties of squares. He did not forget you, his best friend and a talented programmer and thus made a problem about squares to challenge your programming ability. The problem is: given a set of N points in the plane, how many squares are there such that all their corners belong to this set?
Now let's show Johnny your skill!
Input
The first line contains t, the number of test cases (about 10). Then t test cases follow.
Each test case has the following form:
- The first line contains an integer N, the number of points in the given set (4 N 500).
- Then N lines follow, each line contains two integers X, Y describing coordinates of a point (-50 X, Y 50).
Output
For each test case, print in a single line the number of squares that have vertices belong to the given set.
Example
Input:
1
7
0 0
0 1
1 0
1 1
1 2
2 1
2 2
Output:
3
Output details:
The three squares are:
(0 0), (0 1), (1 1), (1 0)
(1 1), (1 2), (2 2), (2 1)
(0 1), (1 0), (2 1), (1 2)
| Author: | admin |
| Date Added: | 28-05-2009 |
| Time Limit: | 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Are all N points guaranteed to be unique?
Will there be duplicate points in the input?
Is there any corner cases like (0 1), (1 0), (2 1), (1 2)
Could not catch tricky cases...
locally, it is working fine even for stress testing.
Folks who submitted any special test case has been considered ???
could anyone help me with the answer for this as input ?
(0,0) (0,1) (0,2) (1,0) (1,2) (2,0)(2,1)(2,2)
Since a sufficiently high number of solutions have been accepted, we would like to leave it up to you to figure out if such cases exist or not and take appropriate action depending on that. In either case, it should not take you more than a couple of submissions to figure the correct way to handle them!
For (0,0) (0,1) (0,2) (1,0) (1,2) (2,0)(2,1)(2,2)..
I think answer is 2.
One squre with (0,0),(0,2)(2,0)(2,2)
another square with (0,1)(1,0)(1,2)(2,1).