首页 > 代码库 > 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 }
View Code