計算幾何 + 統計 Parallelogram Counting

Parallelogram Counting
Time Limit: 5MS   Memory Limit: 65536K
Total Submissions: 5749   Accepted: 1934

Description

There are n distinct points in the plane, given by their integer coordinates. Find the number of parallelograms whose vertices lie on these points. In other words, find the number of 4-element subsets of these points that can be written as {A, B, C, D} such that AB CD, and BC AD. No four points are in a straight line.

Input

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases. It is followed by the input data for each test case.
The first line of each test case contains an integer n (1 <= n <= 1). Each of the next n lines, contains 2 space-separated integers x and y (the coordinates of a point) with magnitude (absolute value) of no more than 1.

Output

Output should contain t lines.
Line i contains an integer showing the number of the parallelograms as described above for test case i.

Sample Input

2
6
0 0
2 0
4 0
1 1
3 1
5 1
7
-2 -1
8 9
5 7
1 1
4 8
2 0
9 8

Sample Output

5
6

 

【题目来源】

Tehran Sharif 2004 Preliminary

http://poj.org/problem?id=1971

【题目大意】

在平面上有n个不同的点,用整数坐标给出。在这些点中寻找平行四边形的数目,也就是找到{A,B,C,D}这样的子集,这些子集满足条件:AB平行于CD,AC平行于BD。不会出现四个点都在一条直线上的情况。输出这样的平行四边形的个数。

【题目分析】

根据平行四边形的性质:对角线互相平分,即:AC与BD有共同的中点。首先求出任意两个点的中点坐标,然后进行排序,最后进行统计。

 

AC代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<bitset>
#define MAX 1010
using namespace std;
struct Node
{
    int x;
    int y;
};
Node node[MAX];
Node mid[500];

bool cmp(Node a,Node b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        int i,j,k;
        for(i=0;i<n;i++)
            scanf("%d%d",&node[i].x,&node[i].y);
        int m=0;
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                mid[m].x=node[i].x+node[j].x;
                mid[m].y=node[i].y+node[j].y;
                m++;
            }
        }
         sort(mid,mid+m,cmp);
         int cnt=0;
         for(i=0;i<m;i++)
         {
             for(j=i+1;j<m;j++)
             {
                 if(mid[i].x==mid[j].x&&mid[i].y==mid[j].y)
                    cnt++;
                    else
                        break;
             }
         }
         printf("%d\n",cnt);
    }
    return 0;
}

 

更多相关文章
一周排行
  • Example 12345678910111213141516171819202122 // vector::data #include <iostream> #include <vector> ...
  • 


    		    Google Chrome 開啓WebGL支持
    首先需要到官网网站下载最新的Google Chrome浏览器,并且安装,下载地址为 htt
  • 1.内核版本检查 [[email protected] SRPMS]# uname -a Linux seker 2.6.2.el5 #1 SMP Tue Jun 10 7 EDT 2008 i686 i68
  • onCreate()方法
    刚才在开发中注意到一个小小的细节,在这里备注一下: onCreate方法在Activity
  • iis錯誤500.19
    这个500.19问题有很多种: 看错误代码: 第一种HRESULT: 0X8007D,是A
  • 


    		    7轉移企業級 Hyperv 群集部署實驗方案
    企业级 高可用性Hyper-v 群集部署实验方案 马博峰 2011年5月21日 -----
  • 终于有点SAP的感觉了.总结下模板 #include<cstdio> #include<cstring> #include<algorithm> #include<queue ...
  • 在使用curl做POST的时候, 当要POST的数据大于1024字节的时候, curl并不会直接就发起POST请求, 而是会分为俩步, 1 发送一个请求, 包含一个Expect:100-continue, 询问Ser ...
  • 360员工桂最近申请了一个长假,一个人背着包出去自助游了. 路上,他经过了一个小镇,发现小镇的人们都围在一棵树下争吵.桂上前询问情况,得知小镇的人们正缺一个镇长,他们希望能选一个知名又公正的镇长,即,大家希望能选出一
  • Linux實用工具Linux監控工具munin的展示(Nginx)
    Munin的安装和配置可以参考第一篇文章: [Linux实用工具]Linux监控工具mun