#include <stdio.h>
#include <stdlib.h>
const long maxn=100000;
const double INFINIT=1000001;
typedef struct
{
	long x1,y1,x2,y2;
	double k;
}point;
point p[maxn];
long n;
typedef struct
{
	int c;
	double k;
}aaa;
aaa a[maxn*10];
__int64 count;
int compare(const void *a,const void *b)
{
	point *x=(point *)a;
	point *y=(point *)b;
	double k=x->k-y->k;
	if(k==0)
	{
		if(x->x1==y->x1)
			return x->x2-y->x2;
		else return x->x1-y->x1;
	}
	else if(k<0)
		return -1;
	return 1;
}
int main()
{
	int N,m,i;
	scanf("%d",&N);
	for(m=0;m<N;m++)
	{
		scanf("%ld",&n);
		for(i=0;i<n;i++)
		{
			scanf("%ld%ld%ld%ld",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2);
			if(p[i].x2==p[i].x1)
				p[i].k=INFINIT;
			else p[i].k=(p[i].y2-p[i].y1)/(p[i].x2-p[i].x1);
		}

		for(i=0;i<maxn*10;i++)
		{
			a[i].c=0;
			a[i].k=-INFINIT;
		}
		qsort(p,n,sizeof(point),compare);
		count=0;
		for(i=0;i<n;i++)
		{
			long j;
			if(a[p[i].x1].k==p[i].k)
				count+=a[p[i].x1].c;
			else
				a[p[i].x1].k=p[i].k;
			for(j=p[i].x1;j<p[i].x2;j++)
				if(a[j].k==p[i].k)
					a[j].c++;
				else
				{
					a[j].c=1;
					a[j].k=p[i].k;
				}
		}
		printf("Scenario #%d:\n",m+1);
		printf("%I64d\n\n",count);
	}
	return 0;
}

• 算法问题 (1418) xfxyjwf 2005-07-24 22:34:30
  • Re:算法问题 (12) eleana 2005-07-25 08:52:13
    • 线段树 (8) 00448242 2005-07-25 11:37:05
• 不是恰好超15MS，是超了那么多，程序就被掐掉了。。。 (1418) wth 2005-07-25 10:24:18