比赛 东方版NOIP模拟赛 评测结果 AAWWAWWAAA
题目名称 Yukari 最终得分 60
用户昵称 一個人的雨 运行时间 0.313 s
代码语言 C++ 内存使用 11.76 MiB
提交时间 2015-10-28 20:15:37
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1000000+10;
int n,zxx,zxy,ysx,ysy,dtx,dty,w,h;
struct point{
	double v;
	int f;
}p[maxn];
int cnt=0;

bool cmp(const point&a,const point&b){
	if (a.v==b.v) return a.f<b.f;
	return a.v<b.v;
}

bool calc(int x,int y,int lim,double &L,double &R){
	if (y==0){if (x<0||x>lim) R=L-1;}
	else if (y>0){
		L=max(L,-(double)x/y);
		R=min(R,(double)(lim-x)/y);
	}
	else{
		L=max(L,(double)(lim-x)/y);
		R=min(R,-(double)x/y);
	}
	return 1;
}

int main(){
	freopen("camera.in","r",stdin);
	freopen("camera.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&zxx,&zxy,&ysx,&ysy);
	dtx=zxx,dty=zxy;
	w=ysx-dtx; h=ysy-dty;
	for (int i=1;i<=n;++i){
		int x,y,xx,yy;
		scanf("%d%d%d%d",&x,&y,&xx,&yy);
		x-=dtx,y-=dty;
		double L=0,R=88888888;
		calc(x,xx,w,L,R);
		calc(y,yy,h,L,R);
		if (R>=L){
			p[++cnt].v=L,p[cnt].f=0;
			p[++cnt].v=R,p[cnt].f=1;
		}
	}
	sort(p+1,p+cnt+1,cmp);
	int now=0,ans=0;
	int tim=0;
	for (int i=1;i<cnt;++i){
		if (!p[i].f){
			now++;
			if (now>ans){
				ans=now;
				tim=p[i].v;
			}
		}
		else now--;
	}printf("%d",tim);
}