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