比赛 |
东方版NOIP模拟赛 |
评测结果 |
WWWWWWWWWW |
题目名称 |
Yukari |
最终得分 |
0 |
用户昵称 |
<蒟蒻>我要喝豆奶 |
运行时间 |
0.322 s |
代码语言 |
C++ |
内存使用 |
2.58 MiB |
提交时间 |
2015-10-28 20:21:58 |
显示代码纯文本
//al:线段树+扫描线最大交集问题
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100000+10;
inline void Update(int x,int a,int w,double &L,double &R){
if(!a){
if(x<=0&&x>=w)
R=L-1;//No answer
}else
if(a>0){
L=max(L,-1*(double)x/a);
R=min(R,(double)(w-x)/a);
}else{
L=max(L,(double)(w-x)/a);
R=min(R,-1*(double)x/a);
}
return ;
}
struct Node{
double x;
int type;
inline friend bool operator < (Node a,Node b){
return a.x<b.x||(a.x==b.x&&a.type>b.type);
}
}events[MAXN<<1];
int main(){
freopen("camera.in","r",stdin);
freopen("camera.out","w",stdout);
int n,x1,y1,x2,y2,w,h,e=0;//转坐标系,让x1 y1为0
scanf("%d%d%d%d%d",&n,&x1,&y1,&x2,&y2);
int dx=x1,dy=x2;
w=x2-dx,h=y2-dx;
for(int i=0;i<n;i++){
int x,y,a,b;
scanf("%d%d%d%d",&x,&y,&a,&b);
x-=dx,y-=dy;
double L=0,R=1e9;
Update(x,a,w,L,R);
Update(y,b,h,L,R);
if(R>L){
events[e++]=(Node){L,0};
events[e++]=(Node){R,1};
}
}sort(events,events+e);
int cnt=0,ans=0;
for(int i=0;i<e;i++){
if(events[i].type==0)
ans=max(ans,++cnt);
else
cnt--;
}
printf("%d",&ans);
return 0;
}