比赛 |
东方版NOIP模拟赛 |
评测结果 |
AAWWWWWWWW |
题目名称 |
Yukari |
最终得分 |
20 |
用户昵称 |
irony |
运行时间 |
0.310 s |
代码语言 |
C++ |
内存使用 |
6.40 MiB |
提交时间 |
2015-10-28 21:54:16 |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn=100005;
struct node{
int x,y,u,v,t1,t2;
node(){}
node(int a,int b,int c,int d,int e,int f)
{x=a;y=b;u=c;v=d;t1=e;t2=f;}
};
struct node2{
int l,r;
node2(){}
node2(int a,int b)
{l=a;r=b;}
};
node e[maxn];
node2 a[maxn];
int n,xl,yl,xr,yr,xi,yi,ui,vi,data[4*maxn],len=0,total=0,time[4*maxn],ans=0;
int ans1=0,ans2=0,time1[205];
void init()
{
scanf("%d%d%d%d%d",&n,&xl,&yl,&xr,&yr);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d",&xi,&yi,&ui,&vi);
e[i]=node(xi,yi,ui,vi,-1,-1);
}
}
int bsearch(int v)
{
int x=1;
int y=len;
while(x<y)
{
int mid=x+(y-x)/2;
if(data[mid]==v) return mid;
if(data[mid]<v) x=mid+1;
else y=mid-1;
}
return x;
}
int doit(int i)
{
int x1,x2,y1,y2,t11,t12,t21,t22,flag1=0,flag2=0;
if(e[i].x<=xl) {x1=xl;x2=xr;flag1=1;}
else if(e[i].x>=xr) {x1=xr;x2=xl;flag1=2;}
if(e[i].x>=xl&&e[i].x<=xr) {t11=0;flag1=0;}
if(e[i].y<=yl) {y1=yl;y2=yr;flag2=1;}
else if(e[i].y>=yr) {y1=yr;y2=yl;flag2=2;}
if(e[i].y>=yl&&e[i].y<=yr) {t21=0;flag2=0;}
long long tmp1,tmp2;
if(flag1)
{
if(e[i].u==0) return 0;
t11=(x1-e[i].x)/e[i].u;
if(t11<0) return 0;
tmp1=t11*e[i].u;
tmp2=x1-e[i].x;
if(tmp1<tmp2)
{
tmp1=(t11+1)*e[i].u;
tmp2=x2-e[i].x;
if(tmp1<=tmp2) t11++;
else return 0;
}
}
if(flag2)
{
if(e[i].v==0) return 0;
t21=(y1-e[i].y)/e[i].v;
if(t21<0) return 0;
tmp1=t21*e[i].v;
tmp2=y1-e[i].y;
if(tmp1<tmp2)
{
tmp1=(t21+1)*e[i].v;
tmp2=y2-e[i].y;
if(tmp1<=tmp2) t21++;
else return 0;
}
}
t12=e[i].u!=0?(x2-e[i].x)/e[i].u:1<<27;
t22=e[i].v!=0?(y2-e[i].y)/e[i].v:1<<27;
int m1=max(t11,t21);
int m2=min(t12,t22);
if(m1>m2) return 0;
e[i].t1=m1;
e[i].t2=m2;
if(m1==0&&m2==1<<27) return 0;
return 1;
}
void repeat()
{
sort(data+1,data+1+len);
int now=data[1],k1=len,k2=len;
for(int i=2;i<=k1;i++)
{
if(data[i]!=now)
{
if(data[i]-now>1)
{
data[++k2]=now+1;
len++;
}
now=data[i];
continue;
}
data[i]=0x7fffffff;
len--;
}
sort(data+1,data+1+k2);
}
void work()
{
for(int i=1;i<=n;i++)
{
if(doit(i))
{
data[++len]=e[i].t1;
data[++len]=e[i].t2;
a[++total]=node2(e[i].t1,e[i].t2);
}
}
repeat();
for(int i=1;i<=total;i++)
{
for(int j=bsearch(a[i].l);j<=bsearch(a[i].r);j++)
{
time[j]++;
}
}
for(int i=1;i<=len;i++)
{
if(time[i]>ans)
{
ans=i;
}
}
printf("%d",data[ans]);
}
void work1()
{
for(int i=1;i<=n;i++)
{
if(doit(i))
{
ans1=max(ans1,e[i].t2);
for(int j=e[i].t1;j<=e[i].t2;j++) time1[j]++;
}
}
for(int i=1;i<=ans1;i++)
{
if(time1[i]>ans2)
{
ans2=i;
}
}
printf("%d",ans2);
}
int main()
{
freopen("camera.in","r",stdin);
freopen("camera.out","w",stdout);
init();
if(n<=101) work1();
else work();
return 0;
}