只WA#21求助
  • 板块CF1046I Say Hello
  • 楼主sgz566
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/11/8 13:33
  • 上次更新2023/11/8 16:33:14
查看原帖
只WA#21求助
378741
sgz566楼主2023/11/8 13:33

交的时候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;
}
2023/11/8 13:33
加载中...