话说AtCoder D卡精度到底怎么卡的?
  • 板块灌水区
  • 楼主冷月葬T魂
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/2/6 21:54
  • 上次更新2023/11/5 03:37:36
查看原帖
话说AtCoder D卡精度到底怎么卡的?
340903
冷月葬T魂楼主2021/2/6 21:54

费尽心思优化精度不得 随手一敲者即得AC

以下是WA代码:

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,val) memset(a,val,sizeof(a))
#define int long long
using namespace std;
 
const int N=1e5+5;
 
signed main()
{
	long double x,y,r;
	cin>>x>>y>>r;
	
	r+=1e-10;
	
	int x1=floor(x-r)-1,x2=ceil(x+r)+1;
	
	int ans1=0;
	
	For(x0,x1,x2){
		long double dx=fabs(x-x0);
		if(dx-r>1e-20) continue;
		long double dy=sqrt(r*r-dx*dx);
		int a=ceil(y-dy),b=floor(y+dy);
		if(a<=b) ans1+=b-a+1;
	}
	
	int yy1=floor(y-r)-1,yy2=floor(y+r)+1;
	
	int ans2=0;
	
	For(yy0,yy1,yy2){
		long double dy=fabs(y-yy0);
		if(dy-r>1e-20) continue;
		long double dx=sqrt(r*r-dy*dy);
		int a=ceil(x-dx-1e-30),b=floor(x+dx+1e-30);
		if(a<=b) ans2+=b-a+1;
	}
	
	cout<<max(ans1,ans2)<<endl;
	
	return 0;
}

以下是AC代码:

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,val) memset(a,val,sizeof(a))
#define int long long
using namespace std;
 
const int N=1e5+5;
 
signed main()
{
	long double x,y,r;
	cin>>x>>y>>r;
	
	r+=1e-14;
	
	int x1=floor(x-r),x2=ceil(x+r);
	
	int ans=0;
	
	For(x0,x1,x2){
		long double dx=x-x0;
		long double cp=r*r-dx*dx;
		if(cp<0.0f) continue;
		long double dy=sqrt(cp);
		int a=ceil(y-dy),b=floor(y+dy);
		if(a<=b) ans+=b-a+1;
	}
	
	
	cout<<ans<<endl;
	
	return 0;
}
2021/2/6 21:54
加载中...