yukicoder : No.635 自然門松列

3問目で手間取ってグダりました。
https://yukicoder.me/problems/no/635

問題

3つの竹が並んでいる。
それぞれ初期状態で長さX[i]であり、時間1毎にY[i]長くなるとする。
3つの竹の長さが門松列を成すタイミングがあるかどうか判定せよ。

解法

門松列の判定は互いの大小だけなので、大小が入れ替わるタイミングの周辺を調べればよい。
以下では

• 時刻0
• とても大きな時刻
• 大小が入れ替わる時刻より少し前後

を判定している。

int N;
long double X[3],Y[3];

int hoge(long double t) {
	double a=X[0]+t*Y[0];
	double b=X[1]+t*Y[1];
	double c=X[2]+t*Y[2];
	if(t<0) return 0;
	
	if(abs(a-b)<1e-12) return 0;
	if(abs(a-c)<1e-12) return 0;
	if(abs(b-c)<1e-12) return 0;
	if(a>b && c>b) return 1;
	if(a<b && c<b) return 1;
	return 0;
}

int ok() {
	
	if(X[0]==X[1] && Y[0]==Y[1]) return 0;
	if(X[0]==X[2] && Y[0]==Y[2]) return 0;
	if(X[1]==X[2] && Y[1]==Y[2]) return 0;
	if(hoge(0)) return 1;
	if(hoge(1<<30)) return 1;
	
	int C[2]={};
	double T=0;
	if(X[0]==X[1] && hoge(1e-5)) return 1;
	if(Y[0]!=Y[1]) {
		T=1.0*(X[1]-X[0])/(Y[0]-Y[1]);
		if(hoge(T+(1e-5))||hoge(T+(1e-6))) return 1;
		if(hoge(T-(1e-5))||hoge(T-(1e-6))) return 1;
	}
	if(X[2]==X[1] && hoge(1e-4)) return 1;
	if(Y[2]!=Y[1]) {
		T=1.0*(X[1]-X[2])/(Y[2]-Y[1]);
		if(hoge(T+(1e-5))||hoge(T+(1e-6))) return 1;
		if(hoge(T-(1e-5))||hoge(T-(1e-6))) return 1;
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	while(N--) {
		cin>>X[0]>>X[1]>>X[2]>>Y[0]>>Y[1]>>Y[2];
		
		if(ok()) _P("YES\n");
		else _P("NO\n");
		
	}
}

まとめ

意外に精度に悩まされました。