> 今天重写了一下～
> 当年是自己写的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;
> }

• 谢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