被卡精度了求助
查看原帖
被卡精度了求助
285617
黑影洞人楼主2023/1/7 23:10
#include<cstdio>
#include<algorithm>
#include<map>
#define N 11451
using namespace std;
const double eps=1e-10;
int n,m;
map<double,double>vis; 
struct tri{
	double x,y,r;
	bool operator<(const tri &t)const{return x<t.x;}
}a[N],tmp[N];
bool fi(tri a,tri b){return a.r<b.r;}
bool fifi(tri a,tri b){return a.x==b.x?a.y<b.y:a.x<b.x;}
int cmp(double x){return x>eps?1:(x<-eps?-1:0);}
bool in(tri a,tri b){
	return b.x>=a.x&&b.x+b.r<=a.x+a.r&&b.y>=a.y&&b.y+b.r<=a.y+a.r&&(cmp(b.x+b.r-a.x-a.y+b.y-a.r)<=0);
}
double f(double x){
	if(vis[x])return vis[x];
	int tot=0;
	for(int i=1;i<=n;i++){
		double l=a[i].x,r=a[i].x+a[i].r,y=a[i].y;
		if(cmp(x-l)>=0&&cmp(r-x)==1){
			double val=r-x;
			if(cmp(val)<=0)continue;
			tmp[++tot]={y,y+val,0};
		}
	}
	if(tot==0)return 0.0; 
	sort(tmp+1,tmp+tot+1,fifi);
	int j=0;
	double ans=0;
	for(int i=1;i<=tot;i=j+1){
		double l=tmp[i].x,r=tmp[i].y;j=i;
		while(j<tot&&tmp[j+1].x<=r)j++,r=max(r,tmp[j].y);
		ans+=r-l;
	}
	return vis[x]=ans;
}
double calc(double l,double r){return (r-l)*(f(l)+4.0*f((l+r)*0.5)+f(r))/6.0;}
double simpson(double l,double r,double ans){
	double mid=(l+r)*0.5;
	double lans=calc(l,mid),rans=calc(mid,r);
	if(!cmp(ans-lans-rans))return lans+rans;
	return simpson(l,mid,lans)+simpson(mid,r,rans);
}
double fz[2*N];
int cnt;
signed main(){
	scanf("%d",&m);
	int cn=0;
	for(int i=1;i<=m;i++){
		double x,y,r;
		scanf("%lf%lf%lf",&x,&y,&r);
		if(r<=0)continue;
		tmp[++cn]={x,y,r};
	}
	sort(tmp+1,tmp+cn+1,fi);a[++n]=tmp[cn];
	fz[++cnt]=tmp[cn].x,fz[++cnt]=tmp[cn].x+tmp[cn].r;
	for(int i=cn-1;i>=1;i--){
		bool flg=0;
		for(int j=1;j<=n&&(!flg);j++)if(in(a[j],tmp[i]))flg=1;
		if(!flg)a[++n]=tmp[i],fz[++cnt]=tmp[i].x,fz[++cnt]=tmp[i].x+tmp[i].r;
	}
	sort(fz+1,fz+cnt+1);
	double ans=0;
	for(int i=2;i<=cnt;i++){
		if(cmp(fz[i]-fz[i-1])>0){
			double l=fz[i-1],r=fz[i]-2*eps;
			ans+=simpson(l,r,calc(l,r));
		}
	}
	printf("%.1lf",(ans*2.0)/2.0);
	return 0;
}



2023/1/7 23:10
加载中...