比赛 东方版NOIP模拟赛 评测结果 AAAAAAAAAA
题目名称 Yukari 最终得分 100
用户昵称 dagger 运行时间 0.307 s
代码语言 C++ 内存使用 6.39 MiB
提交时间 2015-10-28 21:52:50
显示代码纯文本
#include<stdio.h>
#include<algorithm>
using namespace std;
const int inf=0x7fffffff;
struct node{
	int s,e;
}po[100010];
int n,xl,yl,xr,yr,xi,yi,cx,cy,ts,te,txs,txe,tys,tye,vx,vy;
int num,pon,px[200010],l[300030],r[300030],w[300030],ma[300030];
int cz(int x){
	int l,r,m;
	l=1;r=num;
	while(l!=r){
		m=(l+r)/2;
		if(x<=px[m])r=m;
		else l=m+1;
	}
	return l;
}
void tree(int x,int pl,int pr){
	int m;
	m=(pl+pr)/2;
	l[x]=pl;r[x]=pr;
	if(pl!=pr){tree(2*x,pl,m);
	           tree(2*x+1,m+1,pr);}
	return;
}
void plus(int x,int pl,int pr){
	if(l[x]==r[x]){w[x]++;return;}
	int m;
	m=(l[x]+r[x])/2;
	if(pr<=m)plus(2*x,pl,pr);
	else if(pl>m)plus(2*x+1,pl,pr);
	else {plus(2*x,pl,m);plus(2*x+1,m+1,pr);}
	return;
}
int answ(int x){
	if(l[x]==r[x]){ma[x]=l[x];return w[x];}
	if(answ(2*x)>=answ(2*x+1)){w[x]=w[2*x];ma[x]=ma[2*x];}
	else {w[x]=w[2*x+1];ma[x]=ma[2*x+1];}
	return w[x];
}
int main(){
	freopen("camera.in","r",stdin);
	freopen("camera.out","w",stdout);
	int i,j;num=1;pon=1;
	scanf("%d%d%d%d%d",&n,&xl,&yl,&xr,&yr);
	for(i=1;i<=n;i++){
		scanf("%d%d%d%d",&xi,&yi,&cx,&cy);
		vx=abs(cx);vy=abs(cy);
		if((xi<xl&&cx<=0)||(xi>xr&&cx>=0))continue;
		if((yi<yl&&cy<=0)||(yi>yr&&cy>=0))continue;
		if(xi<xl){txs=(xl-xi)/vx;if((xl-xi)%vx)txs++;txe=(xr-xi)/vx;}
		if(xi>xr){txs=(xi-xr)/vx;if((xi-xr)%vx)txs++;txe=(xi-xl)/vx;}
		if(xi>=xl&&xi<=xr&&cx>0){txs=0;txe=(xr-xi)/vx;}
		if(xi>=xl&&xi<=xr&&cx<0){txs=0;txe=(xi-xl)/vx;}
		if(yi<yl){tys=(yl-yi)/vy;if((yl-yi)%vy)tys++;tye=(yr-yi)/vy;}
        if(yi>yr){tys=(yi-yr)/vy;if((yi-yr)%vy)tys++;tye=(yi-yl)/vy;}
        if(yi>=yl&&yi<=yr&&cy>0){tys=0;tye=(yr-yi)/vy;}
        if(yi>=yl&&yi<=yr&&cy<0){tys=0;tye=(yi-yl)/vy;}
		if(cx==0&&xi>=xl&&xi<=xr){txs=0;txe=inf;}if(cy==0&&yi>=yl&&yi<=yr){tys=0;tye=inf;}
		ts=max(txs,tys);te=min(txe,tye);
		if(ts>te)continue;//printf("%d %d\n",ts,te);
		px[num++]=ts;px[num++]=te;po[pon].s=ts;po[pon++].e=te;
	}
	pon--;
	sort(px+1,px+num);
	for(i=1,j=1;j<num;i++){while(px[j]==px[i]&&j<=num)j++;if(j<num)px[i+1]=px[j];}
	num=i-1;//for(i=1;i<=num;i++)printf("%d ",px[i]);printf("%d",num);
	tree(1,1,num);
	for(i=1;i<=pon;i++){plus(1,cz(po[i].s),cz(po[i].e));}
	int maxn=answ(1);
	printf("%d\n",px[ma[1]]);
	//for(j=1;j<=2*num;j++)printf("%d %d\n",w[j],ma[j]);printf("\n");
	return 0;
}