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