[2016-04-15][codeforces][660][D][Number of Parallelograms]

• 时间:2016-04-15 18:40:17 星期五

• 题目编号:[2016-04-15][codeforces][660][D][Number of Parallelograms]

• 题目大意:给定n个点的坐标,问这些点能组成多少个平行四边形

• 分析:

  • 每个平行四边形对角线互相平分,所以只要两条边的交点一样,那么这两条边(斜边)所对应的四边形就一定是平行四边形
  • 所以,枚举所有交点,计算相同交点的个数 Cnti$Cn{t}_i$,那么ans=∑Cnti×(Cnti?1)2$ans=\sum \frac{Cn{t}_i\times (Cn{t}_i?1)}{2}$

• 遇到的问题:

  • 为了方便,计算交点的时候,没有除以2,但是在把点转换成一个数字来存的时候,x坐标乘了 1E9 ,应该乘2×1E9才对
  • 第一次计数用了map来计算,但是时间花了2000+ms,
  • 然后发现有100+ms,就是不用map存,直接把所有交点加入数组中,然后排序,计算相同点的个数

//234ms
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int maxn = 2000 + 10;
struct Point{
        int x,y;
}p[maxn];
long long  q[maxn*maxn];
int main(){
        int n;
        scanf("%d",&n);
        for(int i = 0 ; i < n ; ++i){
                scanf("%d%d",&p[i].x,&p[i].y);
        }
        int cnt = 0;
        memset(q,-1,sizeof(q));
        for(int i = 0 ; i < n ; ++i){
                for(int j = i + 1 ; j < n ; ++j){
                        long long k =((long long) p[i].x + p[j].x)*1E9*2 + (p[i].y) + p[j].y;
                        q[cnt++] = k;
                }
        }
        sort(q , q + cnt);
        int k,ans = 0;
        for(int i = 0 ; i < cnt - 1 ;++i){
                k = 1;
                while(i < cnt && q[i] == q[i + 1]){
                        ++i;++k;
                }
                ans += k * (k - 1) / 2;
        }
        printf("%d\n",ans);
        return 0;
}

//2214ms
#include<cstdio>
#include<map>
using namespace std;
struct Point{
        int x,y;
        Point(int a = 0,int b = 0):x(a),y(b){}
}p[2000 + 10];
map<long long,int > m;
int main(){
        int n;
        scanf("%d",&n);
        for(int i = 0 ; i < n ; ++i){
                scanf("%d%d",&p[i].x,&p[i].y);
        }
        for(int i = 0 ; i < n ; ++i){
                for(int j = i + 1 ; j < n ; ++j){
                        long long k =((long long) p[i].x + p[j].x)*1E9*2 + (p[i].y) + p[j].y;
                        if(m.find(k) == m.end() ){
                                m[k] = 1;
                        }else ++m[k];
                }
        }
        map<long long,int>::iterator itm;
        int ans = 0;
        for(itm = m.begin(); itm != m.end();++itm){
                int n = itm -> second;
                ans += n * (n - 1) / 2;
        }
        printf("%d\n",ans);
        return 0;
}

[2016-04-15][codeforces][660][D][Number of Parallelograms]

原文：http://www.cnblogs.com/qhy285571052/p/7c0e4bdf3744c4bab7f02dc1547fc831.html