首页 > 代码库 > POJ2002 二分查找&哈希
POJ2002 二分查找&哈希
问题重述：
给定整数n，以及n个点的坐标xi, yi。求这n个点可以组成的正方形的数目（每个点可重复使用）。
分析：
根据正方形的性质，给定两个点就能确定可能构成的两个正方形的另外两个顶点。因此，只需要遍历所有点中的两个顶点，计算出可构成正方形的另外两个顶点的坐标，再在已知点中查找这两个点是否存在即可算出正方形数目。
AC代码：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int maxn = 1010; 9 int n;10 11 struct node 12 {13 int x, y;14 bool operator < (const node n) const {15 if ( x != n.x )16 return x < n.x;17 else 18 return y < n.y;19 }20 }star[maxn];21 22 bool search(int x, int y)23 {24 int low = 0;25 int high = n;26 while (low <= high) {27 int mid = (low + high) / 2;28 if (star[mid].x == x && star[mid].y == y)29 return true;30 else {31 if (x < star[mid].x || (x == star[mid].x && y < star[mid].y ))32 high = mid - 1;33 else 34 low = mid + 1;35 }36 }37 return false;38 }39 40 node s1, s2, s3, s4;41 42 void compute(int a, int b)43 {44 int xa = star[a].x;45 int xb = star[b].x;46 int ya = star[a].y;47 int yb = star[b].y;48 s1.x = xa - yb + ya;49 s1.y = ya + xb - xa;50 s2.x = xb - yb + ya;51 s2.y = yb + xb - xa;52 53 s3.x = xa + yb - ya;54 s3.y = ya - xb + xa;55 s4.x = xb + yb - ya;56 s4.y = yb - xb + xa;57 }58 59 int main()60 {61 while (scanf("%d", &n) && n) {62 for (int i = 0; i < n; i++) {63 scanf("%d%d", &star[i].x, &star[i].y);64 }65 sort(star, star + n);66 int ans = 0;67 for (int i = 0; i < n; i++)68 for (int j = i + 1; j < n; j++) {69 compute(i, j);70 if (search(s1.x, s1.y) && search(s2.x, s2.y))71 ans++;72 if (search(s3.x, s3.y) && search(s4.x, s4.y))73 ans++;74 }75 ans /= 4;76 printf("%d\n", ans);77 }78 return 0;79 }
此代码对于所有的点进行二分查找以确定指定点是否存在，因此效率并不高。假如用h[i]存储横坐标为i的点的纵坐标，在通过在h[i]中二分查找指定点是否存在，应该能够大幅提升效率。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。