みけCATのにっき（仮）
つれづれなるまゝに、日くらし、PCにむかひて、心に移りゆくよしなし事を、そこはかとなく書きつくれば、あやしうこそものぐるほしけれ。
（本当か！？）
出典

JAG Ringsの自分の解き方

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:
みけCAT に連絡する

JAG Ringsの自分の解き方

投稿記事 by みけCAT » 12年前

2013年4月21日に行われたJapan Alumni Group Spring Contest 2013。
この中に、Ringsという問題があります。
内容は、2個の輪が鎖のようにつながっているかを判定するもの。所謂普通の幾何です。

自分は、これは他の問題と違って数学をやるだけだと思い、全力で数学してFirst ACを得ました。
こちらがそのコードです。

CODE: 

#include 
#include 

#define EPS (1e-7)

int main(void) {
	double cx1,cy1,cz1;
	double vx11,vy11,vz11,vx12,vy12,vz12;
	double cx2,cy2,cz2;
	double vx21,vy21,vz21,vx22,vy22,vz22;

	double a1,b1,c1,d1,a2,b2,c2,d2;
	double delta;
	double p1,p2,p3,p4;
	double eq_a,eq_b,eq_c,eq_D;
	double x1,y1,z1,x2,y2,z2;
	double dist1,dist2;

	scanf("%lf%lf%lf",&cx1,&cy1,&cz1);
	scanf("%lf%lf%lf%lf%lf%lf",&vx11,&vy11,&vz11,&vx12,&vy12,&vz12);
	scanf("%lf%lf%lf",&cx2,&cy2,&cz2);
	scanf("%lf%lf%lf%lf%lf%lf",&vx21,&vy21,&vz21,&vx22,&vy22,&vz22);

	/* gaiseki */
	a1=vy11*vz12-vy12*vz11;
	b1=vz11*vx12-vz12*vx11;
	c1=vx11*vy12-vx12*vy11;
	a2=vy21*vz22-vy22*vz21;
	b2=vz21*vx22-vz22*vx21;
	c2=vx21*vy22-vx22*vy21;

	/* ax+by+cz=d */
	d1=a1*cx1+b1*cy1+c1*cz1;
	d2=a2*cx2+b2*cy2+c2*cz2;

	delta=b1*c2-b2*c1;
	if(-EPS<=delta && delta<=EPS) {
		/* heikou or itti */
		puts("NO");
		return 0;
	}
	p1=(c2*d1-c1*d2)/delta;
	p2=(a2*c1-a1*c2)/delta;
	p3=(b1*d2-b2*d1)/delta;
	p4=(a1*b2-a2*b1)/delta;

	eq_a=p2*p2+p4*p4+1;
	eq_b=-2*cx1-2*cy1*p2+2*p1*p2+2*p3*p4-2*cz1*p4;
	eq_c=cx1*cx1+cy1*cy1+p1*p1-2*cy1*p1+cz1*cz1+p3*p3-2*cz1*p3-1;
	eq_D=eq_b*eq_b-4*eq_a*eq_c;
	if(eq_D<0+EPS) {
		puts("NO");
		return 0;
	}
	x1=(-eq_b+sqrt(eq_D))/(2*eq_a);
	x2=(-eq_b-sqrt(eq_D))/(2*eq_a);
	y1=p1+p2*x1;
	z1=p3+p4*x1;
	y2=p1+p2*x2;
	z2=p3+p4*x2;
	dist1=(cx2-x1)*(cx2-x1)+(cy2-y1)*(cy2-y1)+(cz2-z1)*(cz2-z1);
	dist2=(cx2-x2)*(cx2-x2)+(cy2-y2)*(cy2-y2)+(cz2-z2)*(cz2-z2);
	if((dist1<1+EPS && 1<dist2+EPS) || (dist2<1+EPS && 1<dist1+EPS)) {
		puts("YES");
	} else {
		puts("NO");
	}
	return 0;
}
一度紙で解き、それをコードに落とし込んだため、これ単体ではよくわかりません。
そこで、紙に書いたメモを整理し、解説PDFの形にしました。これを添付します。

その後公式解説が上がっていたので見てみる。
・・・
え？座標変換？
正規直交行列って何？3次元の回転行列なんて覚えてない！
行列のT乗みたいなマークって何？逆行列そのものなら普通に-1乗って書くよね？やっぱり違うものだよね？
円と直線の交点か…これはなんとなくわかるかも…
頭　悪　い[要出典]
・・・
まあ、ACはACだしいいや。(おい)
添付ファイル

[拡張子 zip は無効化されているため、表示できません]

ページトップ
コメントはまだありません。