poj 2002二分查找方法

题意：在平面内给出n个点，问你这些点一共能组成几个不相等的正方形？

思路：几何 + 二分。先排序，然后枚举任意两点(x1,y1)(x2,y2)，则如果存在点(x1+y1-y2,y1-x1+x2)(x2+y1-y2,y2-x1+x2)则它们能构成一个正方形(这里方向是确定的，否则还有一种可能)。所以用二分查询是否存在这两个点，有的话ans就+1。最后的ans要/2，因为正方形都重复算了一次。

poj 2002二分查找方法
关于二分查找的代码如下:

#include<iostream>
#include<algorithm>
using namespace std;

const int Max = 1005;
struct data
{
	int x, y;
}node[Max];

 

bool cmp(const data &a, const data &b)
{    //  由于下面调用的binary_search()，故要用加const。 
    if(a.x == b.x) 
		return a.y < b.y;
    return a.x < b.x;
}
int main()
{
    int n, i, j;
    while(scanf("%d", &n) && n)
	{
        for(i = 0; i < n; i ++)
            scanf("%d%d", &node[i].x, &node[i].y);
        sort(node, node + n, cmp);      

        //  先排序。这里自己要注意：x相等的y问题不用二维的二分，直接cmp，要理解清楚，就一顺序。
        int ans = 0;
        for(i = 0; i < n; i ++)
            for(j = i + 1; j < n; j ++)
			{
                data tmp;
                tmp.x = node[i].x + node[i].y - node[j].y;
                tmp.y = node[i].y - node[i].x + node[j].x;
                if(!binary_search(node, node + n, tmp, cmp))   //  学会STL的二分。
                    continue;
                tmp.x = node[j].x + node[i].y - node[j].y;
                tmp.y = node[j].y - node[i].x + node[j].x;
                if(!binary_search(node, node + n, tmp, cmp))
                    continue;
                ans ++;
            }
        printf("%d\n", ans/2);
    }
    return 0;
}

至于本题关于hash的算法将会进一步阐述……

poj 2002二分查找方法

相关推荐