记录编号	200835	评测结果	AAAAAAAAAA
题目名称	Yukari	最终得分	100
用户昵称	h0309	是否通过	通过
代码语言	C++	运行时间	0.490 s
提交时间	2015-10-29 16:45:47	内存使用	6.39 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
	int l,r;
}tree[400010];
struct dian{
	int x,y;
}a[100010];
struct di{
	int x,k;
}aa[200010];
int ans[200010];
bool cmp(const di &x,const di &y){
	return x.x<y.x;
}
int erfen(int x,int l,int r){
	int m;
	while(l<r){
		m=l+(r-l)/2;
		if(aa[m].x>=x) r=m;
		else l=m+1;
	}
	return aa[l].k;
}
int main(){
	freopen("camera.in","r",stdin);
	freopen("camera.out","w",stdout);
	int n,xl,yl,xr,yr,k1=0,k2=0,maxn=0x7fffffff,maxa=0,kk;
	scanf("%d%d%d%d%d",&n,&xl,&yl,&xr,&yr);
	for(int q=1;q<=n;q++){
		int x,y,u,v,t1x,t2x,t1y,t2y,t1,t2;
		scanf("%d%d%d%d",&x,&y,&u,&v);
		if(u==0){
			if(x>xr||x<xl) continue;
			else{t1x=0;t2x=maxn;}
		}
		else if(u>0){
			if(x>xr) continue;
			else{
				if(x>=xl) t1x=0;
				else t1x=(xl-x+u-1)/u;
				t2x=(xr-x)/u;
			}
		}
		else{
		    u=-u;
			if(x<xl) continue;
			else{
				if(x<=xr) t1x=0;
				else t1x=(x-xr+u-1)/u;
				t2x=(x-xl)/u;
			}
		}
		if(v==0){
			if(y>yr||y<yl) continue;
			else{t1y=0;t2y=maxn;}
		}
		else if(v>0){
			if(y>yr) continue;
			else{
				if(y>=yl) t1y=0;
				else t1y=(yl-y+v-1)/v;
				t2y=(yr-y)/v;
			}
		}
		else{
		    v=-v;
			if(y<yl) continue;
			else{
				if(y<=yr) t1y=0;
				else t1y=(y-yr+v-1)/v;
				t2y=(y-yl)/v;
			}
		}
		t1=max(t1x,t1y);
		t2=min(t2x,t2y);
		aa[++k1].x=t1;aa[++k1].x=t2;
		a[++k2].x=t1;a[k2].y=t2;
	}
	sort(aa+1,aa+k1+1,cmp);
	aa[0].x=maxn+1;
	for(int i=1,j=0;i<=k1;i++){
	    if(aa[i].x>aa[i-1].x) j++;
	    aa[i].k=j;
	}
	for(int i=1;i<=k2;i++){a[i].x=erfen(a[i].x,1,k1);a[i].y=erfen(a[i].y,1,k1);}
	//for(int i=1;i<=k2;i++) printf("%d %d ",a[i].x,a[i].y);
	for(int i=1;i<=k2;i++){
		ans[a[i].x]++;
		ans[a[i].y+1]--;
	}
	for(int i=2;i<=k1;i++){
	    ans[i]+=ans[i-1];
	    if(ans[i]>maxa){maxa=ans[i];kk=i;}
	}
	//printf("\n");
	for(int i=1;i<=k1;i++)
	    if(aa[i].k==kk){printf("%d",aa[i].x);break;}
	return 0;
}