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

试试看排序前先把数组随机一下

Posted by hawk at 2005-08-14 11:03:13 on Problem 1971
In Reply To:弱问各位……sort()这儿我是不是又错了? Posted by:Ikki at 2005-08-14 11:01:19
> 今天重写了一下~
> 当年是自己写的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;
> }

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