#include "stdio.h"
#include "stdlib.h"
#include "memory.h"
int		sum=0,flag,b[100000];
struct	seg{
	int		x1;
	int		y1;
	int		x2;
	int		y2;
	float	x;
	float	point;	
};
seg		a[100001];
int	 compare(const void *arg1,const void *arg2)
{
	if((*(seg *)arg1).x==(*(seg *)arg2).x)	
	{
		if((*(seg *)arg1).point==(*(seg *)arg2).point)
			return (*(seg *)arg1).x1-(*(seg *)arg2).x1;
		else
			return (int )((*(seg *)arg1).point-(*(seg *)arg2).point);
	}
	else
		return (int)((*(seg *)arg1).x-(*(seg *)arg2).x);
}
int	fd(int x,int n)
{
	int	l=0,r=n,mid=(r+l)/2;
	if(x>b[n])
		return n+1;
	while(!(x>b[mid]&&x<=b[mid+1]))
		{
			if(x<b[mid])
			{
				l=mid,mid=(l+r)/2;
			}
			else
			{
				r=mid,mid=(l+r)/2;
			}
		}
	return mid+1;
}
void main(void)
{
	int		t,n,i,j,temp,k,m,p;
	scanf("%d",&t);
	for(i=1;i<=t;i++)
	{
		scanf("%d",&n);
		for(j=0;j<n;j++)
		{
			scanf("%d%d%d%d",&a[j].x1,&a[j].y1,&a[j].x2,&a[j].y2);
			if(a[j].x1==a[j].x2)
			{	
				a[j].x=1000001;
				a[j].point=(float)a[j].x1;
				if(a[j].y1<=a[j].y2)
					a[j].x1=a[j].y1,a[j].x2=a[j].y2;
				else
					a[j].x1=a[j].y2,a[j].x2=a[j].y1;
			}
			else
			{
				a[j].x=(float)(a[j].y2-a[j].y1)/(a[j].x2-a[j].x1);
				a[j].point=a[j].y1-a[j].x*a[j].x1;
				if(a[j].x1>a[j].x2)
				{
					temp=a[j].x1,a[j].x1=a[j].x2,a[j].x2=temp;
				}
			}
		}
		qsort(a,n,sizeof(seg),compare);
		for(j=0,sum=0;j<n-1;)
		{									
				k=j+1;
				if(a[k].x==a[j].x&&a[k].point==a[j].point&&k<n)
				{
					int m=2;
					b[0]=a[j].x1,b[1]=a[j+1].x1,k++;
					while(a[k].x==a[j].x&&a[k].point==a[j].point&&k<n)
						b[m++]=a[k].x1,k++;	
					for(p=0;p<m;p++)
						sum+=fd(a[j+p].x2,m-1);
					sum-=(1+m)*m/2;
				}			
				j=k;			
		}
		printf("Scenario #%d:\n%d\n\n",i,sum);
	}
}

• 线段树才是王道 (1994) semonteer 2005-09-14 21:51:33
  • 能帮我看看哪里的时间多了啊，实在是想不出啊，好象就一次快排的时间啊， (0) zerocool_08 2005-09-14 21:58:01
  • 能帮我看看哪里的时间多了啊，实在是想不出啊，好象就一次快排的时间啊， (0) zerocool_08 2005-09-14 21:58:03