AOJProblem Set from CGL 問0～4 - c21coterie @ ウィキ

Points/Vectors - Projection

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_A
正射影を求める問題。
指定されている有効桁数が大きいことだけに注意。
あとはベクトルの知識からすぐに式がたちます。

#include<stdio.h>
#include<math.h>

int main(){
	double x0,y0,x1,y1,x2,y2;
	double dx1,dy1,dx2,dy2,lenP1;
	scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
	dx1=x1-x0;
	dy1=y1-y0;
	lenP1=hypot(dx1,dy1);
 	int q;
	scanf("%d",&q);
	while(q--){
		scanf("%lf %lf",&x2,&y2);
		dx2=x2-x0;
		dy2=y2-y0;
		double T=(dx1*dx2+dy1*dy2)/(lenP1*lenP1);
		printf("%.10lf %.10lf\n",x0+dx1*T,y0+dy1*T);
	}
}

Points/Vectors - Reflection

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_B
線対称な点を求める問題。
正射影で求めた点の点対称な位置ですので前の問題のコードを流用します。

#include<stdio.h>
#include<math.h>

int main(){
	double x0,y0,x1,y1,x2,y2;
	double dx1,dy1,dx2,dy2,lenP1;
	scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
	dx1=x1-x0;
 	dy1=y1-y0;
	lenP1=hypot(dx1,dy1);
	int q;
	scanf("%d",&q);
	while(q--){
		scanf("%lf %lf",&x2,&y2);
		dx2=x2-x0;
		dy2=y2-y0;
		double T=(dx1*dx2+dy1*dy2)/(lenP1*lenP1);
		double tx=x0+T*dx1;
 		double ty=y0+T*dy1;
		printf("%.10lf %.10lf\n",tx*2-x2,ty*2-y2);
	}
}

Points/Vectors - Counter-Clockwise

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C
ベクトルAからみてベクトルBが時計回りか反時計回りかもしくは同一直線状にあるなら細かく判断する問題。

#include<stdio.h>
#include<math.h>

int main(){
	double x0,y0,x1,y1,x2,y2;
	double dx1,dy1,dx2,dy2,len1,len2;
	scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
	dx1=x1-x0;
	dy1=y1-y0;
	len1=hypot(dx1,dy1);
	int q;
	scanf("%d",&q);
	while(q--){
		scanf("%lf %lf",&x2,&y2);
		dx2=x2-x0;
		dy2=y2-y0;
		double R=dx1*dy2-dx2*dy1;
 		len2=hypot(dx2,dy2);
		if(R>0){
			printf("COUNTER_CLOCKWISE\n");
		}else if(R<0){
			printf("CLOCKWISE\n");
		}else{
			if(dx1*dx2+dy1*dy2<0){
				printf("ONLINE_BACK\n");
			}else{
				if(len1<len2){
					printf("ONLINE_FRONT\n");
 				}else{
					printf("ON_SEGMENT\n");
				}
			}
		}
 		
	}
}

Segments/Lines - Parallel/Orthogonal

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A
内積が0になれば直交。
外積が0になれば平行。
どちらでもなければ0.

#include<stdio.h>
#include<math.h>

int main(){
	double x0,y0,x1,y1,x2,y2,x3,y3;
	double dx1,dx3,dy1,dy3;
	int q;
	scanf("%d",&q);
	while(q--){
		scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
		scanf("%lf %lf %lf %lf",&x2,&y2,&x3,&y3);
		dx1=x1-x0;
		dy1=y1-y0;
		dx3=x3-x2;
		dy3=y3-y2;
		double R1=(dx1*dy3-dx3*dy1);
	double R2=(dx1*dx3+dy1*dy3);
		if(R1==0){
			printf("2");
		}else if(R2==0){
 			printf("1");
		}else{
			printf("0");
 		}
		printf("\n");
	}
}

Segments/Lines - Intersection

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_B
同一直線上に２本の線がある場合の判定で結構困った問題。
採点データを作った人の掌の上で踊ってしまった感じがする。
勉強になりました。

#include<stdio.h>
#include<math.h>

bool isFlat(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3){
double dx1,dy1,dx2,dy2,dx3,dy3,R1,R2;	
 	dx1=x1-x0;
	dy1=y1-y0;
	dx2=x2-x0;
dy2=y2-y0;
 	dx3=x3-x0;
	dy3=y3-y0;
R1=dx1*dx2+dy1*dy2;	
	R2=dx1*dx3+dy1*dy3;
	if(R1<=0&&0<=R2)return true;
	if(R2<=0&&0<=R1)return true;
	return false;
}
 
bool isCrossHerf(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3){
 	double dx1,dy1,dx2,dy2,dx3,dy3;
	dx1=x1-x0;
	dy1=y1-y0;
	dx2=x2-x0;
	dy2=y2-y0;
	dx3=x3-x0;
	dy3=y3-y0;
	double R1=dx1*dy2-dx2*dy1;
	double R2=dx1*dy3-dx3*dy1;
	if(0<R1&&R2<=0)return true;
	if(0<=R1&&R2<0)return true;
	if(0<R2&&R1<=0)return true;
	if(0<=R2&&R1<0)return true;
	if(R1==0&&R2==0){
		bool Hit1=isFlat(x0,y0,x1,y1,x2,y2,x3,y3);
		bool Hit2=isFlat(x1,y1,x0,y0,x2,y2,x3,y3);
 		bool Hit3=isFlat(x2,y2,x3,y3,x0,y0,x1,y1);
		bool Hit4=isFlat(x3,y3,x2,y2,x0,y0,x1,y1);
		return Hit1||Hit2||Hit3||Hit4;
	}
	return false;
}

int main(){
	double x0,y0,x1,y1,x2,y2,x3,y3;
	double dx1,dx3,dy1,dy3;
	int q;
 	scanf("%d",&q);
	while(q--){
		scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
		scanf("%lf %lf %lf %lf",&x2,&y2,&x3,&y3);
 		bool ok=isCrossHerf(x0,y0,x1,y1,x2,y2,x3,y3)&&isCrossHerf(x2,y2,x3,y3,x0,y0,x1,y1);
		printf("%d\n",ok?1:0);
	}
}