首页 > 代码库 > poj2002Squares(点集组成正方形数)
poj2002Squares(点集组成正方形数)
链接
可以枚举两个点,因为是正方形两外两点可以由已知求出,据说可以根据三角形全等求出下列式子,数学渣不会证。。。
已知: (x1,y1) (x2,y2)
则: x3=x1+(y1-y2) y3= y1-(x1-x2)
x4=x2+(y1-y2) y4= y2-(x1-x2)
或
x3=x1-(y1-y2) y3= y1+(x1-x2)
x4=x2-(y1-y2) y4= y2+(x1-x2)
然后就可以hash或者二分做了,这里只用hash做的
应该算是简单的hash解决冲突的应用,放一个邻接表里。
两点需正反枚举两次,才能保证两种位置的正方形都被枚举到。
最后的结果需要除4,因为重复枚举了。
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 using namespace std;11 #define N 101012 #define mod 9999113 #define LL long long14 #define INF 0xfffffff15 const double eps = 1e-8;16 const double pi = acos(-1.0);17 const double inf = ~0u>>2;18 struct point19 {20 int x,y;21 point(int x=0,int y=0):x(x),y(y){}22 }p[N],o[N];23 int next[N],head[mod],t;24 void insert(int i)25 {26 int key = (p[i].x*p[i].x+p[i].y*p[i].y)%mod;27 next[t] = head[key];28 o[t].x = p[i].x;29 o[t].y = p[i].y;30 head[key] = t++;31 }32 int find(point a)33 {34 int key = (a.x*a.x+a.y*a.y)%mod;35 int i;36 for(i = head[key] ; i!= -1 ; i = next[i])37 {38 if(o[i].x==a.x&&o[i].y == a.y) return 1;39 }40 return 0;41 }42 bool cmp(point a,point b)43 {44 if(a.x==b.x)45 return a.y<b.y;46 return a.x<b.x;47 }48 int main()49 {50 int n,i,j;51 while(scanf("%d",&n)&&n)52 {53 memset(head,-1,sizeof(head));54 t = 0;55 for(i = 1; i <= n; i++)56 {57 scanf("%d%d",&p[i].x,&p[i].y);58 insert(i);59 }60 //sort(p+1,p+n+1,cmp);61 int ans = 0;62 for(i = 1; i <= n ;i++)63 for(j = 1 ; j <= n; j++)64 {65 if(i==j) continue;66 point p1,p2;67 p1.x = p[i].x+(p[i].y-p[j].y);68 p1.y = p[i].y-(p[i].x-p[j].x);69 p2.x = p[j].x+(p[i].y-p[j].y);70 p2.y = p[j].y-(p[i].x-p[j].x);71 if(!find(p1)) continue;72 if(!find(p2)) continue;73 ans++;74 }75 printf("%d\n",ans/4);76 }77 return 0;
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。