CF double 奇怪的问题
查看原帖
CF double 奇怪的问题
133060
henryhu2006楼主2022/12/11 13:37

如果把这个代码用 CF 上的 c++14 交上去会 WA Test 4,输出 -1。如果用 c++17 Diagnosis 发现 Test 4 是能过的。最后发现是浮点数误差问题以后就过了 Accepted

但是问题就来了,一开始第一个代码在 Test 4 输出 -1,我把第一个代码中开头的结构体函数

inline double operator * (const node aa)const{
		double pos=0;
		if(aa.k==k) pos=(aa.b==b)?max(s,aa.s):1e18;
		else pos=1.*(aa.b-b)/(k-aa.k);
		return (inr(pos)&&aa.inr(pos))?pos:1e18;
	}

里面加了一行调试语句,其实输出任何东西都行,printf, cout, cerr, puts 之类都行,加进去,放到 CF custom innovation 里面测一下,最后一行输出的都是正确结果。请问是不是开了 O2 优化以后 double 发生了什么奇怪的问题?

修改以后变成:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
double c[N*2],now,ans=1e18;
struct node{
	double s,t,k,b;
	inline double cal(double x)const{ return k*x+b;}
	inline double inr(double x)const{ return x>=s&&x<=t;}
	inline bool operator < (const node aa)const{ return cal(now)<aa.cal(now);}
	inline bool operator == (const node aa)const{ return cal(now)==aa.cal(now);}
	inline double operator * (const node aa)const{
		double pos=0;
		if(aa.k==k) pos=((aa.b==b)?max(s,aa.s):1e18);
		else pos=1.*(aa.b-b)/(k-aa.k);
    	puts("gg");
		return (pos>=s&&pos<=t&&pos>=aa.s&&pos>=aa.t)?pos:1e18;
	}
};
multiset<node> s;
vector<node> vec1[N*2],vec2[N*2];
void solve(vector<node> vec){
	int top=0; s.clear();
	for(auto &z:vec)
		z.b-=z.k*z.s,c[++top]=z.s,c[++top]=z.t;
	sort(c+1,c+top+1);
	int tg=top; top=0; c[0]=-1e9;
	for(int i=1;i<=tg;++i)
		if(c[i]-c[i-1]>1e-8) c[++top]=c[i];
	for(int i=top+1;i<=tg;++i) c[i]=-1e9;
	for(int i=1;i<=top;++i)
		vec1[i].clear(),vec2[i].clear();
	for(auto z:vec){
		int ps=lower_bound(c+1,c+top+1,z.s)-c;
		int pt=lower_bound(c+1,c+top+1,z.t)-c;
		if(fabs(z.s-c[ps])>fabs(z.s-c[ps-1])) --ps;
		if(fabs(z.t-c[pt])>fabs(z.t-c[pt-1])) --pt;
		vec1[ps].emplace_back(z);
		vec2[pt].emplace_back(z);
	}
	for(int i=1;i<=top&&c[i]<ans;++i){
		now=c[i];
		for(auto z:vec1[i]){
			s.insert(z);
			auto it=s.find(z),is=it;
			if(it!=s.begin()) is=it,--is,ans=min(ans,(*is)*(*it)); is=it;
			if((++is)!=s.end()) ans=min(ans,(*is)*(*it));
		}
		for(auto z:vec2[i]){
			auto it=s.find(z),is=it,ir=it;
			++ir;
			if(ir!=s.end()&&it!=s.begin()) --is,ans=min(ans,(*is)*(*ir));
			s.erase(it);
		}
	}
}

int n,m,son[N],sz[N],dfn[N],dfncl,d[N],f[N],top[N];
vector<int> e[N];
vector<node> vc[N];
void dfs1(int u,int fa){
	f[u]=fa,sz[u]=1;
	for(int v:e[u]){
		if(v==fa) continue;
		dfs1(v,u),sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int fa,int tp){
	dfn[u]=++dfncl,top[u]=tp,d[u]=d[fa]+1;
	if(son[u]) dfs2(son[u],u,tp);
	for(int v:e[u])
		if(v!=fa&&v!=son[u]) dfs2(v,u,v); 
}
int dist(int u,int v){
	int res=0;
	for(;top[u]!=top[v];res+=d[u]-d[top[u]]+1,u=f[top[u]])
		if(d[top[u]]<d[top[v]]) swap(u,v);
	return res+abs(d[u]-d[v]);
}
void add(int v,int u,double s,int c){
	double t=s+1.*dist(u,v)/c;
	for(;top[u]!=top[v];)
		if(d[top[u]]>d[top[v]]){
			vc[top[u]].emplace_back(
				(node){t-1.*(d[u]-d[top[u]]+1)/c,t,1.*c,1.*(d[top[u]]-1)});
			t-=1.*(d[u]-d[top[u]]+1)/c,u=f[top[u]];
		}
		else{
			vc[top[v]].emplace_back(
				(node){s,s+1.*(d[v]-d[top[v]]+1)/c,-1.*c,1.*d[v]});
			s+=1.*(d[v]-d[top[v]]+1)/c,v=f[top[v]];
		}

	vc[top[u]].emplace_back(
		(node){s,t,1.*(d[v]>d[u]?-c:c),1.*d[v]});
}
int main(){
	cin>>n>>m;
	for(int i=1,u,v;i<n;++i){
		scanf("%d%d",&u,&v);
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	dfs1(1,0),dfs2(1,0,1);
	for(int i=1,t,c,v,u;i<=m;++i)
		scanf("%d%d%d%d",&t,&c,&v,&u),add(v,u,t,c);
	for(int i=1;i<=n;++i)
		if(vc[i].size()) solve(vc[i]);
	if(ans>2e4) puts("-1");
	else printf("%.10lf",ans); 
	return 0;
} 

但在第一个代码本地和洛谷 IDE 上、CF C++17 Diagnosis 上输出都是对的,所以是不是 CF 的 C++14 有问题啊?

2022/12/11 13:37
加载中...