今天重写了一下～
当年是自己写的qsort()
结果……2.5s ac
然后改成stl sort()
结果巨慢无比……
4.6s才a掉……

各位大牛～告诉我为什么
//1971.cpp
//Parallelogram Counting

//By phoenixinter
//On 8/14/2005

#include<stdio.h>
#include<algorithm>
using namespace std;

struct Point
{
	int x,y;
} p[1001];

struct segment
{
	double s,l;
} seg[500001];

int partition(int p,int r)
{
	int i=p,j=r+1;
	segment x=seg[p];
	while(true)
	{
		while(seg[++i].s<x.s||(seg[i].s==x.s&&seg[i].l<x.l));
		while(seg[--j].s>x.s||(seg[j].s==x.s&&seg[j].l>x.l));
		if(i>=j) break;
		segment temp=seg[i];
		seg[i]=seg[j];
		seg[j]=temp;
	}
	seg[p]=seg[j];
	seg[j]=x;
	return j;
}

void qsort(int p,int r)
{
	if(p<r)
	{
		int q=partition(p,r);
		qsort(p,q-1);
		qsort(q+1,r);
	}
}

bool operator < (segment a,segment b)
{
	return a.s<b.s||(a.s==b.s&&a.l<b.l);
}

int main()
{
	int t,i,j,no,n=0,count,sum;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&no);
		for(i=1;i<=no;i++)
			scanf("%d %d",&p[i].x,&p[i].y);
		n=0;
		for(i=1;i<=no-1;i++)
			for(j=i+1;j<=no;j++)
			{
				seg[++n].s=(double)(p[i].x+p[j].x)/2;
				seg[n].l=(double)(p[i].y+p[j].y)/2;
			}
		//printf("n:%d\n",n);
		sort(seg+1,seg+n+1);
		//qsort(1,n);
		/*
		for(i=1;i<=n;i++)
			printf("%lf %lf\n",seg[i].s,seg[i].l);
		*/
		count=0,sum=0;
		for(i=2;i<=n;i++)
		{
			if(seg[i].s==seg[i-1].s&&seg[i].l==seg[i-1].l)
				count++;
			else
			{
				sum+=count*(count+1)/2;
				count=0;
			}
		}
		printf("%d\n",sum);
	}
	return 0;
}

• 试试看排序前先把数组随机一下 (1719) hawk 2005-08-14 11:03:13
  • 谢hawk，不过我原来的qsort()也没有随机啊……还有stl sort没有randomize吗？ (0) Ikki 2005-08-14 11:04:51
    • 哦，你是说你写的比库函数快啊 (78) hawk 2005-08-14 11:08:14
      • 而且你取比较值得方式和qsort不一定一样，这样对于特定数据，效果就会不同了 (88) hawk 2005-08-14 11:09:33
  • 或者说你取比较那个值的时候随机取，应该效果也一样 (26) hawk 2005-08-14 11:05:49
    • gosh^^^这个问题真奇怪……撒…… (30) Ikki 2005-08-14 11:11:59