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