Count the squares

https://www.codechef.com/problems/D6
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?

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)

https://www.codechef.com/status/D6
https://www.codechef.com/viewsolution/10228421

1. public static void main(String[] args) throws IOException {
2. Locale.setDefault(Locale.US);
3. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
4. PrintWriter out = new PrintWriter(System.out,true);
5. Point c = new Point();
6. Point d = new Point();
7. int n = Integer.parseInt(br.readLine());
8. for (int i=0; i<n; i++) {
9. int k = Integer.parseInt(br.readLine());
10. List<Point> points = new ArrayList<Point>(k);
11. Set<Point> set = new HashSet<Point>(2*k);
12. for (int j=0; j<k; j++) {
13. String s = br.readLine().trim();
14. int index = s.indexOf(' ');
15. int x = Integer.parseInt(s.substring(0,index));
16. int y = Integer.parseInt(s.substring(index+1));
17. Point p = new Point(x,y);
18. points.add(p);
19. set.add(p);
20. }
21. int count = 0;
22. for (int x=0; x<k; x++) {
23. Point a = points.get(x);
24. for (int y=x+1; y<k; y++) {
25. Point b = points.get(y);
26. int dx = b.x-a.x;
27. int dy = b.y-a.y;
28. c.x = b.x-dy;
29. c.y = b.y+dx;
30. d.x = c.x-dx;
31. d.y = c.y-dy;
32. if (set.contains(c) && set.contains(d)) {
33. count++;
34. }
35. c.x = b.x+dy;
36. c.y = b.y-dx;
37. d.x = c.x-dx;
38. d.y = c.y-dy;
39. if (set.contains(c) && set.contains(d)) {
40. count++;
41. }
42. }
43. }
44. out.println(count/4);
45. }
46. out.close();
47. }