比赛 |
东方版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;
}