首页 > 代码库 > poj1971Parallelogram Counting
poj1971Parallelogram Counting
链接
越来越感觉到了数学的重要性!。。
这题本来用以斜率和长度为key值进行hash不过感觉很麻烦还TLE了。。
最后知道中点一样的话就可以组成平行四边形,初中数学就可以了。。
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 #include<map>11 using namespace std;12 #define N 101013 #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 } p[N],o[N*N];22 23 bool cmp(point a,point b)24 {25 if(a.x==b.x) return a.y<b.y;26 return a.x<b.x;27 }28 int main()29 {30 int t,n,i,j;31 cin>>t;32 while(t--)33 {34 scanf("%d",&n);35 for(i = 1 ; i <= n ; i++)36 {37 scanf("%d%d",&p[i].x,&p[i].y);38 }39 int g = 0;40 for(i = 1 ; i<= n ; i++)41 {42 for(j = i+1 ; j <= n ;j++)43 {44 o[++g].x = (p[i].x+p[j].x);45 o[g].y = (p[i].y+p[j].y);46 // cout<<o[g].y<<endl;47 }48 }49 LL ans = 0;50 sort(o+1,o+g+1,cmp);51 int e = 1;52 for(i = 2; i <= g ;i++)53 {54 if(o[i].x-o[i-1].x==0&&o[i].y-o[i-1].y==0)55 {56 e++;57 // cout<<o[i].x<<" ,"<<o[i-1].x<<" "<<o[i].y<<" "<<o[i-1].y<<endl;58 }59 else60 {61 ans+=(LL)(e-1)*e/2;62 e = 1;63 }64 }65 ans+=(LL)(e-1)*e/2;66 cout<<ans<<endl;67 }68 return 0;69 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。