首页 > 代码库 > poj1971Parallelogram Counting

poj1971Parallelogram Counting

2024-07-04 20:35:01   225人阅读

题意：给定平面上的n个点，求这n个点中能构成平行四边形的个数。

     保证不会有四个点在同一条直线上。

解题思路：由于平行四边形的两条对角线交于一点，且该点为两对角线的中点。若两线段的中点是同一个点，则这两条线段的四个顶点一定可以构成一个平行四边形！

所以可以求所有线段的中点，然后根据相同中点的个数来判断平行四边形的个数。如果一个点重复了k次，则形成的平行四边形的个数为k(k-1)/2.

 1 //Accepted    16888 KB    980 ms
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 const int MAXN = 1005;
 8 int n;
 9 struct node
10 {
11     double x,y;
12 }p[MAXN*MAXN],e[MAXN];
13 int num;
14 void pre()
15 {
16     for (int i=0;i<n;i++)
17     {
18         scanf("%lf%lf",&e[i].x,&e[i].y);
19     }
20     for (int i=0;i<n;i++)
21     {
22         for (int j=i+1;j<n;j++)
23         {
24             p[num].x=(e[i].x+e[j].x)/2;
25             p[num++].y=(e[i].y+e[j].y)/2;
26         }
27     }
28 }
29 int cmp(struct node x,struct node y)
30 {
31     if (x.x==y.x)
32     {
33         return x.y<y.y;
34     }
35     else
36     return x.x<y.x;
37 }
38 int slove()
39 {
40     int ans=0;
41     sort(p,p+num,cmp);
42     int temp=1;
43     struct node pp=p[0];
44     for (int i=1;i<num;i++)
45     {
46         if (p[i].x==pp.x && p[i].y==pp.y)
47         {
48             temp++;
49         }
50         else
51         {
52             ans+=temp*(temp-1)/2;
53             pp.x=p[i].x;
54             pp.y=p[i].y;
55             temp=1;
56         }
57     }
58     return ans;
59 }
60 int main()
61 {
62     int T;
63     scanf("%d",&T);
64     for (int t=1;t<=T;t++)
65     {
66         scanf("%d",&n);
67         num=0;
68         pre();
69         printf("Case %d: %d\n",t,slove());
70     }
71     return 0;
72 }
View Code

 


联系
我们