> #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;
> }
> 

• Re:算法问题 (12) eleana 2005-07-25 08:52:13
  • 线段树 (8) 00448242 2005-07-25 11:37:05