Poj Solution 1971

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

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define debug 0

#define INF 30000

#if debug
    #define NMAX 10    
#else
    #define NMAX 1003
#endif
typedef struct
{
    int x,y;
}point;
point a[NMAX],m[NMAX*NMAX];
int cmp(const void*a,const void *b)
{
    if((*(point*)a).x==(*(point*)b).x)
        return (*(point*)a).y-(*(point*)b).y;
    else 
        return (*(point*)a).x-(*(point*)b).x;
}

int main()
{

#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int t,n,i,j,M,ans,c,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y);
        }
        k=0;
        for(i=0;i<n;i++) 
        {
            for(j=i+1;j<n;j++)
            {
                
                
                    m[k].x=(a[i].x+a[j].x);
                    m[k].y=(a[i].y+a[j].y);
                    k++;
                 
            }
        }
        qsort(m,k,sizeof(point),cmp);
        ans=0;
        c=1;
        for(i=1;i<k;i++)
        {
            if(m[i].x==m[i-1].x&&m[i].y==m[i-1].y)
                c++;
            else
            { 
                ans+=c*(c-1)/2;
                c=1;
            }
        }
//        ans+=c*(c-1)/2;
        printf("%dn",ans);
    }
#if debug
    fclose(stdin);
    fclose(stdout);
#endif
    return 1;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *