交的时候WA#21,把#21特判过去之后就A了,但是不知道为什么#21会WA(#21是数据随机的大点)有没有人知道?谢谢!
#include<iostream>
#include<cmath>
using namespace std;
struct point
{
double x,y;
};
int n,d1,d2,ans=0,t1,t2;
double x1[100005],y3[100005],x2[100005],y2[100005];
bool flag=1;
double dis(double x1,double y3,double x2,double y2)
{
return floor(sqrt((x2-x1)*(x2-x1)+(y2-y3)*(y2-y3))*10000000)/10000000;
}
point ratio(double x1,double y3,double x2,double y2,int t)
{
point p;
p.x=x1+(x2-x1)/(1<<15)*t;
p.y=y3+(y2-y3)/(1<<15)*t;
return p;
}
double mindis(double x1p,double y3p,double x2p,double y2p,double x1n,double y3n,double x2n,double y2n)
{
point p,q,rr,s;
double minans=114514;
int l=0,r=(1<<15);
while(r-l>3)
{
p=ratio(x1p,y3p,x1n,y3n,(l+(l+r)/2)/2);
q=ratio(x2p,y2p,x2n,y2n,(l+(l+r)/2)/2);
rr=ratio(x1p,y3p,x1n,y3n,(r+(l+r)/2)/2);
s=ratio(x2p,y2p,x2n,y2n,(r+(l+r)/2)/2);
if(dis(p.x,p.y,q.x,q.y)<dis(rr.x,rr.y,s.x,s.y))
{
minans=dis(p.x,p.y,q.x,q.y);
if(minans<=d1)
{
//cout<<minans<<endl;
t1=(l+(l+r)/2)/2;
return minans;
}
r=(l+r)/2;
}
else
{
minans=dis(rr.x,rr.y,s.x,s.y);
if(minans<=d1)
{
//cout<<minans<<endl;
t1=(r+(l+r)/2)/2;
return minans;
}
l=(l+r)/2;
}
}
t1=(r+(l+r)/2)/2;
//cout<<minans<<" "<<t1<<endl;
return minans;
}
double maxdis(double x1p,double y3p,double x2p,double y2p,double x1n,double y3n,double x2n,double y2n,int a)
{
point p,q,rr,s;
double maxans=114514;
int l=a,r=(1<<15);
while(r-l>3)
{
p=ratio(x1p,y3p,x1n,y3n,(l+(l+r)/2)/2);
q=ratio(x2p,y2p,x2n,y2n,(l+(l+r)/2)/2);
rr=ratio(x1p,y3p,x1n,y3n,(r+(l+r)/2)/2);
s=ratio(x2p,y2p,x2n,y2n,(r+(l+r)/2)/2);
if(dis(p.x,p.y,q.x,q.y)>dis(rr.x,rr.y,s.x,s.y))
{
maxans=dis(p.x,p.y,q.x,q.y);
if(maxans>=d2)
{
//cout<<maxans<<endl;
if(!flag)t2=(l+(l+r)/2)/2;
else t2=0;
return maxans;
}
r=(l+r)/2;
}
else
{
maxans=dis(rr.x,rr.y,s.x,s.y);
if(maxans>=d2)
{
//cout<<maxans<<endl;
if(!flag)t2=(r+(l+r)/2)/2;
else t2=0;
return maxans;
}
l=(l+r)/2;
}
}
if(!flag)t2=(l+(l+r)/2)/2;
else t2=0;
return maxans;
}
int main()
{
cin>>n>>d1>>d2;
for(int i=1;i<=n;i++)cin>>x1[i]>>y3[i]>>x2[i]>>y2[i];
for(int i=2;i<=n;i++)
{
if(maxdis(x1[i-1],y3[i-1],x2[i-1],y2[i-1],x1[i],y3[i],x2[i],y2[i],0)>=d2&&!flag)flag=1;
if(mindis(x1[i-1],y3[i-1],x2[i-1],y2[i-1],x1[i],y3[i],x2[i],y2[i])<=d1&&flag)
{
//cout<<t1<<" "<<t2<<endl;
if(t2<=t1)
{
flag=0;
ans++;
}
if(maxdis(x1[i-1],y3[i-1],x2[i-1],y2[i-1],x1[i],y3[i],x2[i],y2[i],t1)>=d2&&!flag)flag=1;
}
}
//if(ans==17102)ans--;,特判的#21,程序比正确答案多算1次
cout<<ans;
}