恒星的正方形问题

 一 原问题描述

Squares - POJ 2002 - Virtual Judgehttps://vjudge.net/problem/POJ-2002

二 输入和输出

1 输入

输入包含多个测试用例。每个测试用例都以整数 n 开始，表示恒星的数量，接下来的 n 行，每行都包含一颗恒星的 x 和 y 坐标（两个整数）。假设这些横恒星的位置是不同的，并且坐标小于 20000.当 n = 0 时，输入终止。

2 输出

对于每个测试用例，都单行输出恒星形成的正方形数。

三 输入和输出样例

1 输入样例

4

1 0

0 1

1 1

0 0

9

0 0

1 0

2 0

0 2

1 2

2 2

0 1

1 1

2 1

4

-2 5

3 7

0 0

5 2

0

2 输出样例

1

6

1

四 分析

如果枚举 4 个节点会超时，可以任意枚举两个点，然后将另两个点算出来，判断是否在已创建的 hash 表里即可，首先枚举（x1，y1）、（x2、y2）两个点，然后以这两个点为边，将所有的左侧和右侧两个点都枚举一次。有以下两种情况，如下图所示，因为正方形内部的几个三角形是相等的，所以可以推导出正方形的另外两个节点（x3，y3）和（x4，y4）。

左侧两点

x3 = x2 - (y1-y2)     y3 = y2 + (x1-x2)

x4 = x1 - (y1-y2)     y4 = y1 + (x1-x2)

右侧两点

x3 = x2 + (y1-y2)     y3 = y2 - (x1-x2)

x4 = x1 + (y1-y2)     y4 = y1 - (x1-x2)

五 算法设计

1 把输入数据放入哈希表

2 根据两个点（x1，y1）、（x2，y2），得到左侧两个点（x3，y3）、（x4、y4），在哈希表中查找这两个点是否存在，如果存在，则 ans++。

3 根据两个点（x1，y1）、（x2，y2），得到左侧两个点（x3，y3）、（x4、y4），在哈希表中查找这两个点是否存在，如果存在，则 ans++。

4 计数时对每个正方形都计数了两次，所以答案除以 2。因为根据两个点（x3，y3）、（x4、y4）也可以得到另外两个点（x1，y1）、（x2、y2）.

六 代码

package poj2002;

import java.util.Scanner;

public class Poj2002 {
    static int N = 1010;
    static int H = 10007;
    static int sx[] = new int[N];
    static int sy[] = new int[N];
    static Node node[] = new Node[N];
    static int n;
    static int cur;
    static int hashTable[] = new int[H];
    static long ans;

    static {
        for (int i = 0; i < node.length; i++) {
            node[i] = new Node();
        }
    }

    static void initHash() {
        for (int i = 0; i < H; i++)
            hashTable[i] = -1;
        cur = 0;
        ans = 0;
    }

    static void insertHash(int x, int y) {
        int h = (x * x + y * y) % H;
        node[cur].x = x;
        node[cur].y = y;
        node[cur].next = hashTable[h];
        hashTable[h] = cur++;
    }

    static boolean searchHash(int x, int y) {
        int h = (x * x + y * y) % H;
        int next = hashTable[h];
        while (next != -1) {
            if (x == node[next].x && y == node[next].y)
                return true;
            next = node[next].next;
        }
        return false;
    }

    public static void main(String[] args) {
        int xx, yy, x1, y1, x2, y2;
        while (true) {
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();

            if (n == 0) {
                return;
            }

            initHash();
            for (int i = 0; i < n; i++) {
                sx[i] = scanner.nextInt();
                sy[i] = scanner.nextInt();
                insertHash(sx[i], sy[i]);
            }
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    xx = sx[i] - sx[j];
                    yy = sy[i] - sy[j];
                    x1 = sx[i] - yy;
                    y1 = sy[i] + xx;
                    x2 = sx[j] - yy;
                    y2 = sy[j] + xx;
                    if (searchHash(x1, y1) && searchHash(x2, y2))
                        ans++;
                    x1 = sx[i] + yy;
                    y1 = sy[i] - xx;
                    x2 = sx[j] + yy;
                    y2 = sy[j] - xx;
                    if (searchHash(x1, y1) && searchHash(x2, y2))
                        ans++;
                }
            }
            System.out.println(ans >>= 2);
        }
    }
}

class Node {
    int x;
    int y;
    int next;
}

七 测试

绿色为输入，白色为输出