Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:sort 排序1000+过了

Posted by 731371663 at 2011-01-17 20:20:21 on Problem 1971
In Reply To:sort 排序1000+过了 Posted by:731371663 at 2011-01-17 20:19:50
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1001;
struct node
{
	int x,y;
}a[N],temp;
node b[N*N/2];//存放中点
bool operator < (const node a,const node b)
{
	if(a.x==b.x)
		return a.y<b.y;
	return a.x<b.x;
}

int main()
{
//	freopen("in.txt","r",stdin);
	int t,n,i,j,sum,k,m;
	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++)
			{
				b[k].x=a[i].x+a[j].x;//计算中点,不除2,用整数处理
				b[k++].y=a[i].y+a[j].y;

			}
		}
		sort(b,b+k);//中的小到大排序
		sum=0;
	    temp.x=b[0].x;
		temp.y=b[0].y;
		for(i=1;i<k;)
		{
			m=1;
			while(temp.y==b[i].y&&temp.x==b[i].x)
			{
				m++;//相同的个数
				i++;
			}
			temp.x=b[i].x;
			temp.y=b[i].y;
			i++;
			if(m>1)
				sum+=m*(m-1)>>1;

		}
		printf("%d\n",sum);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator