Parallelogram Counting http://poj.org/problem?id=1971
题意: 输入 t 表示有 t 组数据
每组数据输入一个数 n, 表示有 n 个点
然后有 n 行, 每行是这个点的 (x,y)
问这些点能组成多少个平行四边形
思路: 求中点, 中点一样的是一个平行四边形.
记录同一个中点的个数 sum(初始为 1), 平行四边形数是 (sum-1) * sum / 2;
- #include<iostream>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- const int inf = 0x3f3f3f3f;
- struct zz
- {
- double x, y;
- };
- zz a[1007];
- zz b[1007 * 1007];
- bool cmp(zz u, zz v)
- {
- if(u.x == v.x) return u.y <v.y;
- return u.x < v.x;
- }
- int main()
- {
- /*freopen("in.txt", "r", stdin);
- freopen("out.txt", "w", stdout);*/
- int n;
- cin>> n;
- while(n--)
- {
- int i, j, m;
- cin>> m;
- for(i = 0; i <m; i++)
- {
- cin>> a[i].x>> a[i].y;
- }
- int k = 0;
- for(i = 0; i < m - 1; i++)
- {
- for(j = i + 1; j < m; j++)
- {
- if(a[i].x == a[j].x && a[i].y == a[j].y) continue;
- b[k].x = (a[i].x + a[j].x) / 2;
- b[k++].y = (a[i].y + a[j].y) / 2;
- }
- }
- sort(b, b + k, cmp);
- int sum = 0, ans = 1;
- for(i = 0; i < k - 1; i++)
- {
- if(b[i].x == b[i + 1].x && b[i].y == b[i + 1].y) ans++;
- else
- {
- sum += (ans - 1) * ans / 2;
- ans = 1;
- }
- }
- cout << sum << endl;
- }
- /*fclose(stdin);
- fclose(stdout);*/
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2584093.html