比赛 东方版NOIP模拟赛 评测结果 AAAAAAAAAA
题目名称 Yukari 最终得分 100
用户昵称 raywzy 运行时间 0.361 s
代码语言 C++ 内存使用 6.41 MiB
提交时间 2015-10-28 21:01:50
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#define LL long long
#define INF 0X7FFFFFFF
#define eps 1e-8
using namespace std;
map<int,int> ma;
vector<int> vec;
int fanxiang[500005];
int line[500005];
struct Node
{
	int x,y,a,b;
}f[100005];
struct Point
{
	double x,y;
};
struct Range
{
	int L,R;
}F[100005];
inline void open()
{
	freopen("camera.in","r",stdin);
	freopen("camera.out","w",stdout);
}
int N,xl,yl,xr,yr;
LL L,R;
inline double dis(double x,double y,double a,double b)
{
	return sqrt((x-a)*(x-a)+(y-b)*(y-b));
}
inline void Cal(Node P)
{
	double k;double b;vector<Point> ff;
	double x1,y1;Point temp;L=-1;R=-1;
	double V=sqrt(P.a*P.a*1.0+P.b*P.b*1.0);
	if(V==0.0)
	{
		if(P.x>=xl&&P.x<=xr&&P.y>=yl&&P.y<=yr)
		{
			L=0;R=0;
		}
		return ;
	}
	if(P.a==0)
		k=0.0;
	else
		k=P.b*1.0/P.a;
	b=P.y-k*P.x;
	x1=xl;y1=k*x1+b;
	if(y1>=yl&&y1<=yr)
	{
		temp.x=x1;temp.y=y1;
		ff.push_back(temp);
	}
	x1=xr;y1=k*x1+b;
	if(y1>=yl&&y1<=yr)
	{
		temp.x=x1;temp.y=y1;
		ff.push_back(temp);
	}
	y1=yl;
	if(k==0.0)
		x1=P.x*1.0;
	else
		x1=(y1-b)/k;
	if(x1>=xl&&x1<=xr)
	{
		temp.x=x1;temp.y=y1;
		ff.push_back(temp);
	}
	y1=yr;
	if(k==0.0)
		x1=P.x*1.0;
	else
		x1=(y1-b)/k;
	if(x1>=xl&&x1<=xr)
	{
		temp.x=x1;temp.y=y1;
		ff.push_back(temp);
	}
	if(ff.size()==0)
	{
		return ;
	}		
	if(P.x>=xl&&P.x<=xr&&P.y>=yl&&P.y<=yr)
	{
		double pa,pb;L=0;R=0;
		for(int i=0;i<ff.size();i++)
		{
			pa=ff[i].x-P.x;
			pb=ff[i].y-P.y;
			if(pa*P.a>0&&pb*P.b>0)
			{
				double tmp=dis(ff[i].x,ff[i].y,P.x*1.0,P.y*1.0)/V;
				L=0;R=int(tmp);
				return ;
			}
		}
	}
	double AA=dis(ff[0].x,ff[0].y,P.x*1.0,P.y*1.0)/V;
	double BB=dis(ff[1].x,ff[1].y,P.x*1.0,P.y*1.0)/V;
	if(AA>BB) swap(AA,BB);
	L=int(ceil(AA-eps)+eps);
	R=int(BB);
	return ;
}
int main()
{
	open();
	scanf("%d%d%d%d%d",&N,&xl,&yl,&xr,&yr);
	for(int i=1;i<=N;i++)
		scanf("%d%d%d%d",&f[i].x,&f[i].y,&f[i].a,&f[i].b);
	for(int i=1;i<=N;i++)
	{
		Node temp;
		temp=f[i];
		Cal(temp);
		F[i].L=L;F[i].R=R;
		if(L==-1&&R==-1) continue;
		if(ma[L]==0)
		{
			ma[L]=1;
			vec.push_back(L);
		}
		if(ma[R]==0)
		{
			ma[R]=1;
			vec.push_back(R);
		}
	}
	int cnt=0;
	sort(vec.begin(),vec.end());
	for(int i=0;i<vec.size();i++)
	{
		cnt++;ma[vec[i]]=cnt;
		fanxiang[cnt]=vec[i];
	}
	for(int i=1;i<=N;i++)
	{
		if(F[i].L==-1&&F[i].R==-1) continue;
		if(F[i].R<F[i].L) continue;
		line[ma[F[i].L]]++;line[ma[F[i].R]+1]--;
	}
	int temp=0;int MAXN=0;
	for(int i=1;i<=cnt;i++)
	{
		temp+=line[i];
		MAXN=max(temp,MAXN);	
	}
	temp=0;int ans=0;
	for(int i=1;i<=cnt;i++)
	{
		temp+=line[i];
		if(temp==MAXN&&ans==0)
			ans=fanxiang[i];		
	}
	printf("%d\n",ans);
	return 0;
}