比赛 东方版NOIP模拟赛 评测结果 AAWWWWWWWW
题目名称 Yukari 最终得分 20
用户昵称 irony 运行时间 0.310 s
代码语言 C++ 内存使用 6.40 MiB
提交时间 2015-10-28 21:54:16
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn=100005;
struct node{
	int x,y,u,v,t1,t2;
	node(){}
	node(int a,int b,int c,int d,int e,int f)
	{x=a;y=b;u=c;v=d;t1=e;t2=f;}
};
struct node2{
	int l,r;
	node2(){}
	node2(int a,int b)
	{l=a;r=b;}
};
node e[maxn];
node2 a[maxn];
int n,xl,yl,xr,yr,xi,yi,ui,vi,data[4*maxn],len=0,total=0,time[4*maxn],ans=0;
int ans1=0,ans2=0,time1[205];

void init()
{
	scanf("%d%d%d%d%d",&n,&xl,&yl,&xr,&yr);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d%d",&xi,&yi,&ui,&vi);
		e[i]=node(xi,yi,ui,vi,-1,-1);
	}
}


int bsearch(int v)
{
	int x=1;
	int y=len;
	while(x<y)
	{
		int mid=x+(y-x)/2;
		if(data[mid]==v) return mid;
		if(data[mid]<v) x=mid+1;
		else y=mid-1;
	}
	return x;
}

int doit(int i)
{
	int x1,x2,y1,y2,t11,t12,t21,t22,flag1=0,flag2=0;
	if(e[i].x<=xl) {x1=xl;x2=xr;flag1=1;}
	else if(e[i].x>=xr) {x1=xr;x2=xl;flag1=2;}
	if(e[i].x>=xl&&e[i].x<=xr) {t11=0;flag1=0;}
	
	if(e[i].y<=yl) {y1=yl;y2=yr;flag2=1;}
	else if(e[i].y>=yr) {y1=yr;y2=yl;flag2=2;}
	if(e[i].y>=yl&&e[i].y<=yr) {t21=0;flag2=0;}
	long long tmp1,tmp2;
	if(flag1)
	{
		if(e[i].u==0) return 0;
		t11=(x1-e[i].x)/e[i].u;
		if(t11<0) return 0;
		tmp1=t11*e[i].u;
		tmp2=x1-e[i].x;
		if(tmp1<tmp2)
		{
		  tmp1=(t11+1)*e[i].u;
		  tmp2=x2-e[i].x;
		  if(tmp1<=tmp2) t11++;
		  else return 0;
	    }
	}
	if(flag2)
	{
		if(e[i].v==0) return 0;
		t21=(y1-e[i].y)/e[i].v;
		if(t21<0) return 0;
		tmp1=t21*e[i].v;
		tmp2=y1-e[i].y;
		if(tmp1<tmp2)
		{
		  tmp1=(t21+1)*e[i].v;
		  tmp2=y2-e[i].y;
		  if(tmp1<=tmp2) t21++;
		  else return 0;
	    }
	}
	
	t12=e[i].u!=0?(x2-e[i].x)/e[i].u:1<<27;
	t22=e[i].v!=0?(y2-e[i].y)/e[i].v:1<<27;
	int m1=max(t11,t21);
	int m2=min(t12,t22);
	if(m1>m2) return 0;
	e[i].t1=m1;
	e[i].t2=m2;
	
	if(m1==0&&m2==1<<27) return 0;
	return 1;
}

void repeat()
{
	sort(data+1,data+1+len);
	int now=data[1],k1=len,k2=len;
	for(int i=2;i<=k1;i++)
	{
		if(data[i]!=now)
		{
		    
			if(data[i]-now>1)
			{
				data[++k2]=now+1;
				len++;
			}
			now=data[i];
			continue;
		}
		data[i]=0x7fffffff;
		len--;
	}
	sort(data+1,data+1+k2);
}

void work()
{
	for(int i=1;i<=n;i++)
	{
		if(doit(i))
		{
			data[++len]=e[i].t1;
			data[++len]=e[i].t2;
			a[++total]=node2(e[i].t1,e[i].t2);
		}
	}
	repeat();
	for(int i=1;i<=total;i++)
	{
		for(int j=bsearch(a[i].l);j<=bsearch(a[i].r);j++)
		{
			time[j]++;
		}
	}
	for(int i=1;i<=len;i++)
	{
		if(time[i]>ans)
		{
			ans=i;
		}
	}
	printf("%d",data[ans]);
}

void work1()
{
	for(int i=1;i<=n;i++)
	{
		if(doit(i))
		{
			ans1=max(ans1,e[i].t2);
			for(int j=e[i].t1;j<=e[i].t2;j++) time1[j]++;
		}
	}
	for(int i=1;i<=ans1;i++)
	{
		if(time1[i]>ans2)
		{
			ans2=i;
		}
	}
	printf("%d",ans2);
}

int main()
{
	freopen("camera.in","r",stdin);
	freopen("camera.out","w",stdout);
	init();
	if(n<=101) work1();
	else work();
	return 0;
}