比赛 东方版NOIP模拟赛 评测结果 AAAWWWWAWA
题目名称 Yukari 最终得分 50
用户昵称 ABCD 运行时间 0.718 s
代码语言 C++ 内存使用 14.80 MiB
提交时间 2015-10-28 21:20:20
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
struct tr{
	int l,r,m,n;
}tree[800005];
struct dian{
	int x,y,vx,vy,t1,t2;
}di[100005];
set<int>se;
set<int>::iterator it;
map<int,int>ma,maa;
int m,n,x1,x2,y1,y2;
int t1(int x){
	int i,j,k,y,z,t1=0,t2=0,t;
	if(di[x].vx>0){
		if(x1>=di[x].x){t1=(x1-di[x].x)/di[x].vx;if((x1-di[x].x)%di[x].vx)t1++;}
	    else if(x2>di[x].x)t1=1000000000;
	    else t1=0;
	}
	else if(di[x].vx<0){
		if(x2<=di[x].x){t1=(x2-di[x].x)/di[x].vx;if((di[x].x-x2)%di[x].vx)t1++;}
	    else if(x1>di[x].x)t1=1000000000;
	    else t1=0;
	}
	else if(di[x].x>=x1&&di[x].x<=x2&&di[x].y>=y1&&di[x].y<=y2){t1=0;}
	else t1=1000000000;
	if(di[x].vy>0){
	    if(di[x].y<=y1){t2=(y1-di[x].y)/di[x].vy;if((y1-di[x].y)%di[x].vy)t2++;}
	    else if(y2<di[x].y)t2=1000000000;
	    else t2=0;
	}
	else if(di[x].vy<0){
		if(y2<=di[x].y){t2=(y2-di[x].y)/di[x].vy;if((y2-di[x].y)%di[x].vy)t2++;}
		else if(y1>di[x].y)t2=1000000000;
		else t2=0;
	}
	else if(di[x].x>=x1&&di[x].x<=x2&&di[x].y>=y1&&di[x].y<=y2){t2=0;}
	else t2=1000000000;
	t=max(t1,t2);
	return t;
}
int t2(int x){
	int i,j,k,y,z,t1=0,t2=0,t;
	//printf("%d %d %d %d\n",di[x].x,di[x].y,di[x].vx,di[x].vy);
	if(di[x].vx>0){
		if(x2>=di[x].x){t1=(x2-di[x].x)/di[x].vx;if((x2-di[x].x)%di[x].vx)t1++;}
	    else if(x2<di[x].x)t1=1000000000;
	}
	else if(di[x].vx<0){
		if(x1<=di[x].x){t1=(x1-di[x].x)/di[x].vx;if((x1-di[x].x)%di[x].vx)t1++;}
	    else if(x1>di[x].x)t1=1000000000;
	}
	else if(di[x].x>=x1&&di[x].x<=x2&&di[x].y>=y1&&di[x].y<=y2){t1=0;}
	else t1=1000000000;
	if(di[x].vy>0){
	    if(di[x].y<=y2){t2=(y2-di[x].y)/di[x].vy;if((y2-di[x].y)%di[x].vy)t2++;}
	    else if(y2<di[x].y)t2=1000000000;
	}
	else if(di[x].vy<0){
		if(y1<=di[x].y){t2=(y1-di[x].y)/di[x].vy;if((y1-di[x].y)%di[x].vy)t2++;}
		else if(y1>di[x].y)t2=1000000000;
	}
	else if(di[x].x>=x1&&di[x].x<=x2&&di[x].y>=y1&&di[x].y<=y2){t2=0;}
	else t2=1000000000;
	t=min(t1,t2);
	return t;
}
void js(){
	int i=0;
	for(i=1;i<=n;i++){
		di[i].t1=t1(i);
		di[i].t2=t2(i);
		
		if(di[i].t1>di[i].t2){
			di[i].t1=1000000000;
		    di[i].t2=1000000000;
		}
		//printf("%d %d\n",di[i].t1,di[i].t2);
		se.insert(di[i].t1);
		se.insert(di[i].t2);
	}
	i=1;
	for(it=se.begin();it!=se.end();it++,i++){
		ma[*it]=i;
		maa[i]=*it;
	}
	for(i=1;i<=n;i++){
		di[i].t1=ma[di[i].t1];
		di[i].t2=ma[di[i].t2];
	}
}
void build(int l,int r,int k){
	tree[k].l=l;
	tree[k].r=r;
	tree[k].n=0;
	tree[k].m=0;
	if(l==r)return;
	int m=(l+r)/2;
	build(l,m,2*k);
	build(m+1,r,2*k+1);
}
void add(int l,int r,int k){
	if(l==tree[k].l&&r==tree[k].r){tree[k].m+=1;return;}
	if(l<tree[2*k+1].l)add(l,tree[2*k].r,2*k);
	if(r>tree[2*k].r)add(tree[2*k+1].l,r,2*k+1);
}
int fin(int x,int k){
	if(x==tree[k].l&&x==tree[k].r)return tree[k].m;
	if(x>tree[2*k].r)return tree[k].m+fin(x,2*k+1);
	if(x<tree[2*k+1].l)return tree[k].m+fin(x,2*k);
}
int main(){
	int x,y,z,i,j,k;
	freopen("camera.in","r",stdin);
	freopen("camera.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&x1,&y1,&x2,&y2);
	for(i=1;i<=n;i++){
		scanf("%d%d%d%d",&x,&y,&z,&k);
		di[i].x=x;
		di[i].y=y;
		di[i].vx=z;
		di[i].vy=k;
	}
	js();
	build(1,se.size(),1);
	for(i=1;i<=n;i++){
		add(di[i].t1,di[i].t2,1);
	}
	x=0;
	y=0;
	for(i=1;i<=se.size();i++){
		if(x<fin(i,1)){x=fin(i,1);y=i;}
	}
	printf("%d",maa[y]);
	return 0;
}