问题重述:
给定整数n,以及n个点的坐标xi, yi。求这n个点可以组成的正方形的数目(每个点可重复使用)。
分析:
根据正方形的性质,给定两个点就能确定可能构成的两个正方形的另外两个顶点。因此,只需要遍历所有点中的两个顶点,计算出可构成正方形的另外两个顶点的坐标,再在已知点中查找这两个点是否存在即可算出正方形数目。
AC代码:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; ; int n; struct node { int x, y; bool operator < (const node n) const { if ( x != n.x ) return x < n.x; else return y < n.y; } }star[maxn]; bool search(int x, int y) { ; int high = n; while (low <= high) { ; if (star[mid].x == x && star[mid].y == y) return true; else { if (x < star[mid].x || (x == star[mid].x && y < star[mid].y )) high = mid - ; else low = mid + ; } } return false; } node s1, s2, s3, s4; void compute(int a, int b) { int xa = star[a].x; int xb = star[b].x; int ya = star[a].y; int yb = star[b].y; s1.x = xa - yb + ya; s1.y = ya + xb - xa; s2.x = xb - yb + ya; s2.y = yb + xb - xa; s3.x = xa + yb - ya; s3.y = ya - xb + xa; s4.x = xb + yb - ya; s4.y = yb - xb + xa; } int main() { while (scanf("%d", &n) && n) { ; i < n; i++) { scanf("%d%d", &star[i].x, &star[i].y); } sort(star, star + n); ; ; i < n; i++) ; j < n; j++) { compute(i, j); if (search(s1.x, s1.y) && search(s2.x, s2.y)) ans++; if (search(s3.x, s3.y) && search(s4.x, s4.y)) ans++; } ans /= ; printf("%d\n", ans); } ; }
此代码对于所有的点进行二分查找以确定指定点是否存在,因此效率并不高。假如用h[i]存储横坐标为i的点的纵坐标,在通过在h[i]中二分查找指定点是否存在,应该能够大幅提升效率。