Source

Problem Id:2489  User Id:zerocool_08 
Memory:11800K  Time:10015MS
Language:C++  Result:Time Limit Exceed

Source 

#include "stdio.h"
#include "stdlib.h"
#include "memory.h"
int		sum=0,flag,b[3000000]={0};
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)				
		return (int )((*(seg *)arg1).point-(*(seg *)arg2).point);

	else
		return (int)((*(seg *)arg1).x-(*(seg *)arg2).x);
}
void insert(int	x)
{
	int		k=1,l=0,r=1000000,mid;
	while(l<r)
	{
		mid = (l + r)/2;
		if(x>mid)
			l=mid+1,k=2*k+1;
		else
			b[k]++,r=mid,k*=2;
	}
	b[k]++;
}
int	fd(int x)
{
	int		k=1,l=0,r=1000000,mid,s=0;
	while(l<r)
	{
		mid =(l+r)/2;
		if(x>mid)
			l=mid+1,s+=b[k],k=2*k+1;
		else
			r=mid,k*=2;
	}
	return s;
}

void main(void)
{
	int		t,n,i,j,temp,k,m;
	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)
				{
					temp=a[j].y1,a[j].y1=a[j].y2,a[j].y2=temp;
				}
			}
			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;)
		{							
			if(a[j].x<1000001)
			{
				k=j+1;
				memset(b,0,sizeof(b));
				insert(a[j].x1);
				while(a[k].x==a[j].x&&a[k].point==a[j].point&&k<n)
						insert(a[k].x1),k++;
				if(k-j>1)
				{					
					for(m=j;m<k;m++)
						sum+=fd(a[m].x2);
					sum-=(k-j+1)*(k-j)/2;
				}			
				j=k;
			}
			else
			{
				k=j+1;
				memset(b,0,sizeof(b));
				insert(a[j].y1);
				while(a[k].x==a[j].x&&a[k].point==a[j].point&&k<n)
					insert(a[k].y1),k++;
				if(k-j>1)
				{
					for(m=j;m<k;m++)
						sum+=fd(a[m].y2);
					sum-=(k-j+1)*(k-j)/2;
				}
				j=k;
			}						
		}
		printf("Scenario #%d:\n%d\n\n",i,sum);
	}
}