首页 > 代码库 > POJ 2002 Squares 计算集合 点的hash
POJ 2002 Squares 计算集合 点的hash
题目大意:给出平面上的n个点,问能组成多少个正方形。
思路:一开始看时间3秒半,就想用set水过,然而失败了。没办法手写hash吧。观察坐标的范围,<20000,样例中还有负的,我们读进来的时候就将点的坐标+20000,这样避免负数,方便hash。我的哈希很弱,就是把xy坐标加起来作为哈希值,想卡的话应该很轻松。但还是过得很快。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1010 using namespace std; struct Point{ int x,y; Point(int _ = 0,int __ = 0):x(_),y(__) {} bool operator ==(const Point &a)const { return (x == a.x && y == a.y); } Point operator -(const Point &a)const { return Point(x - a.x,y - a.y); } Point operator +(const Point &a)const { return Point(x + a.x,y + a.y); } void Read() { scanf("%d%d",&x,&y); x += 20000,y += 20000; } }point[MAX]; struct HashSet{ int head[80010],total; int next[MAX]; Point val[MAX]; void Insert(const Point &p) { int x = p.x + p.y; next[++total] = head[x]; val[total] = p; head[x] = total; } bool Find(const Point &p) { int x = p.x + p.y; for(int i = head[x]; i; i = next[i]) if(val[i] == p) return true; return false; } void Clear() { memset(head,0,sizeof(head)); total = 0; } }hash; int points; int main() { while(scanf("%d",&points),points) { for(int i = 1; i <= points; ++i) { point[i].Read(); hash.Insert(point[i]); } int ans = 0; for(int i = 1; i <= points; ++i) for(int j = i + 1; j <= points; ++j) { Point v = point[j] - point[i]; Point _v(v.y,-v.x); if(hash.Find(point[i] + _v) && hash.Find(point[j] + _v)) ++ans; Point __v(-v.y,v.x); if(hash.Find(point[i] + __v) && hash.Find(point[j] + __v)) ++ans; } printf("%d\n",ans / 4); hash.Clear(); } return 0; }
POJ 2002 Squares 计算集合 点的hash
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。