POJ2002---正方形

POJ2002---正方形

​​题目描述​​

正方形是边长相等且相邻边形成90度角的4边多边形。它也是一个多边形，围绕其中心旋转 90 度会得到相同的多边形。然而，它不是唯一具有后一特性的多边形，因为正八边形也具有此特性。

所以我们都知道正方形是什么样子的，但是我们能找到所有可能由夜空中的一组星星组成的正方形吗？为了使问题更容易，我们假设夜空是一个二维平面，每颗星星都由它的 x 和 y 坐标指定。

输入

输入由许多测试用例组成。每个测试用例以整数 n (1 <= n <= 1000) 开始，表示要跟踪的点数。接下来的 n 行中的每一行都指定了每个点的 x 和 y 坐标（两个整数）。您可以假设点是不同的，并且坐标的大小小于 20000。当 n = 0 时，输入终止。

输出

对于每个测试用例，在一行上打印一个人可以从给定的星星形成的正方形数。

Sample Input

41 00 11 10 090 01 02 00 21 22 20 11 12 14-2 53 70 05 20

Sample Output

161

思路分析

题目分析:直接将四个点枚举会超时,所以任意枚举两个点,将任意两个点算出来后判断是否在自己创建的hash表中.可以按照什么规则呢?如下图所示,我们把两个点当成相邻边的点,我们可以算出其他两个点的坐标.

假设x1,x2,x3,x4的输入顺序是x1,x2,x3,x4则在进行枚举时(先以右上正方形为例)对于一个正方形会被ans++四次.

i-->x1;j-->x2;i-->x1;j-->x4;i-->x2;j-->x3;i-->x3;j-->x4

当枚举到这四种情况时,都可以在hashTab中找到该正方形的其他两点,并且这四种情况对应的是同一个正方形. 同理左下正方形也是这个规律. 所以最终结果ans要 / 4;

参考代码

//POJ2002#includeusing namespace std;const int N=1010;const int H=10007;int ptx[N],pty[N];struct Node{ int x; int y; int next;}; Node node[N];int cur;//控制当前静态链表的下标的 int n;long ans;//统计数目int hashTab[H];void initHash() //这里不能使用memset因为这个仅对字符数组有效 { for(int i = 0;i>n&&n){ initHash(); for(int i = 0;i>=2; printf("%ld\n",ans); } return 0; }

注意:本题使用线性探测法会出现多个数据堆积,然后运行超时.

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。