LightOJ 1058 平行四边形的判断定理

题目大意：给你n个点，求这n个点最多能组成多少个平行四边形。

题目思路：这道题卡时间，而且卡内存。你要尽可能的想办法优化。

平行四边形的判定定理：

两组对边分别平行的四边形是平行四边形（定义判定法）；
一组对边平行且相等的四边形是平行四边形；
两组对边分别相等的四边形是平行四边形；
两组对角分别相等的四边形是平行四边形（两组对边平行判定）；
对角线互相平分的四边形是平行四边形。

这道题用定理5判断。

记录每条边的中点坐标，如果两个边的中点坐标相同，证明这两条边为一个平行四边形的两条对角线。

#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f
#define MAX 1000005

using namespace std;

struct node
{
    double midx,midy;
    int x,y;
}Map[MAX];

int cmp(node A,node B)
{
    if(A.midx != B.midx)
        return A.midx > B.midx;
    return A.midy > B.midy;
}
int main()
{
    int T,n,i,j,num=1,k;
    long long sum,cnt,q;
    scanf("%d",&T);
    while(T--)
    {
        sum=0;
        cnt=0;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&Map[i].x,&Map[i].y);
        }

        for(i=1;i<=n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                Map[cnt].midx=(Map[i].x+Map[j].x)/2.0;
                Map[cnt++].midy=(Map[i].y+Map[j].y)/2.0;
            }
        }

        sort(Map,Map+cnt,cmp);//为了后面的操作更省时，先排序

        i=0;
        k=0;
        q=1;
        while(i < cnt)
        {
            if(Map[i].midx==Map[k].midx && Map[i].midy==Map[k].midy && k!=i)
                {
                    sum+=q;//新增加的边可以与之前的每一条拥有相同中点的边形成一个新的平行四边形
                    q++;
                }
            else if(Map[i].midx!=Map[k].midx || Map[i].midy!=Map[k].midy)
            {
                k=i;
                q=1;
            }
            i++;
        }
        printf("Case %d: %lld
",num++,sum);
    }
    return 0;
}

View Code

LightOJ 1058 平行四边形的判断定理

相关推荐